Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235562] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK, Partitioning arrangements of lines II: Applications, Discrete & Computational Geometry, vol. 5 no. 1 (1990), pp. 533-573, ISSN 0179-5376 [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 "red-blue" 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 Springer-Verlag New York Inc.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320