Math @ Duke

Publications [#235562] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK, Partitioning arrangements of lines II: Applications,
Discrete & Computational Geometry, vol. 5 no. 1
(1990),
pp. 533573, ISSN 01795376 [doi]
(last updated on 2017/12/15)
Abstract: In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) an O(m2/3n2/3 · log2/3n · logω/3 (m/√n)+(m+n) log n) algorithm to compute all incidences between m points and n lines, where ω is a constant <3.33; (ii) an O(m2/3n2/3 · log5/3n · logω/3 (m/√n)+(m+n) log n) algorithm to compute m faces in an arrangement of n lines; (iii) an O(n4/3 log(ω+2)/3n) algorithm to count the number of intersections in a set of n segments; (iv) an O(n4/3 log(ω + 2)/3n) algorithm to count "redblue" intersections between two sets of segments, and (v) an O(n3/2 logω/3n) algorithm to compute spanning trees with low stabbing number for a set of n points. We also present an algorithm that, given set of n points in the plane, preprocesses it, in time O(n√m logω+1/2n), into a data structure of size O(m) for n log n≤m≤n2, so that the number of points of S lying inside a query triangle can be computed in O((n/√m) log3/2n) time. © 1990 SpringerVerlag New York Inc.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

