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

Math @ Duke



Publications [#235385] of Pankaj K. Agarwal

Papers Published

  1. 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. 67-75
    (last updated on 2018/10/22)

    We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional 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 three-dimensional case the expected running time is O(nk2 + min(n log3 n, nk2 log n)). The algorithm also works for computing the ≤k-level 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 order-k 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).
ph: 919.660.2800
fax: 919.660.2821

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