Math @ Duke

Publications [#235385] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Berg, MD; Matousek, J; Schwarzkopf, O, Constructing levels in arrangements and higher order Voronoi diagrams,
in Tenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(1994),
pp. 6775
(last updated on 2018/03/22)
Abstract: We give a simple lazy randomized incremental algorithm to compute ≤klevels in arrangements of xmonotone Jordan curves in the plane, and in arrangements of planes in threedimensional space. If each pair of curves intersects in at most s points, the expected running time of the algorithm is O(k2λs(n/k) + min(λs(n) log2 n, k2λs(n/k) log n)). For the threedimensional case the expected running time is O(nk2 + min(n log3 n, nk2 log n)). The algorithm also works for computing the ≤klevel in a set of discs, with an expected running time of O(nk + min(n log2 n, nk log n)). Furthermore, we give a simple algorithm for computing the orderk Voronoi diagram of a set of n points in the plane that runs in expected time O(k(n  k) log n + n log3 n).


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

