Constructing levels in arrangements and higher order Voronoi diagrams


Journal Article

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).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; de Berg, M; Matousek, J; Schwarzkopf, O

Published Date

  • January 1, 1994

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 67 - 75

Digital Object Identifier (DOI)

  • 10.1145/177424.177521

Citation Source

  • Scopus