### Abstract

The kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E^{2} subdivides E^{2} into maximal regions such that all points within a given region have the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in O(n^{2} log n + k(n - k) log^{2} n) time, O(k(n - k)) storage, and in O(n^{2}+ k(n - k) log^{2} n) time, O(n^{2}) storage, respectively.

Original language | English (US) |
---|---|

Pages (from-to) | 1349-1354 |

Number of pages | 6 |

Journal | IEEE Transactions on Computers |

Volume | C-36 |

Issue number | 11 |

DOIs | |

State | Published - Nov 1987 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics

### Keywords

- Arrangements of lines and planes
- Euclidean and projective space
- Voronoi diagrams
- computational geometry
- geometric transforms
- maintenance of convex hulls

## Fingerprint Dive into the research topics of 'An Improved Algorithm for Constructing kth-Order Voronoi Diagrams'. Together they form a unique fingerprint.

## Cite this

Hazelle, B., & Edelsbrunner, H. (1987). An Improved Algorithm for Constructing kth-Order Voronoi Diagrams.

*IEEE Transactions on Computers*,*C-36*(11), 1349-1354. https://doi.org/10.1109/TC.1987.5009474