# Constructing levels in arrangements and higher order Voronoi diagrams

Published

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

### 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

### Citation Source

- Scopus