### Abstract

The kth-order Voronoi diagram of a set of points o 2 in E (called sites) subdivides E into maximal regions such that each point within a given region has 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 1n O{n2logn+k(n-k)log^{2}n) time, 0(k(n-k)) storage, and O(n^{2}+k(n-k)log^{2}n) time,O(n) storage,.

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

Title of host publication | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |

Publisher | Association for Computing Machinery, Inc |

Pages | 228-234 |

Number of pages | 7 |

ISBN (Electronic) | 0897911636, 9780897911634 |

DOIs | |

State | Published - Jun 1 1985 |

Externally published | Yes |

Event | 1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985 |

### Publication series

Name | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|

### Other

Other | 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|---|

Country | United States |

City | Baltimore |

Period | 6/5/85 → 6/7/85 |

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Geometry and Topology

## Fingerprint Dive into the research topics of 'An improved algorithm for constructing k<sup>th</sup>-qrder voronoi diagrams'. Together they form a unique fingerprint.

## Cite this

Chazelle, B., & Edelsbrunner, H. (1985). An improved algorithm for constructing k

^{th}-qrder voronoi diagrams. In*Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985*(pp. 228-234). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323263