Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
We present linear-time algorithms to construct tree-like Voronoi diagrams with disconnected regions after the sequence of their faces along an enclosing boundary (or at infinity) is known. We focus on the farthest-segment Voronoi diagram, however, our techniques are also applicable to constructing the order-(k+1) subdivision within an order-k Voronoi region of segments and updating a nearest-neighbor Voronoi diagram of segments after deletion of one site. Although treestructured, these diagrams illustrate properties surprisingly different from their counterparts for points. The sequence of their faces along the relevant boundary forms a Davenport-Schinzel sequence of order ≥ 2. Once this sequence is known, we show how to compute the corresponding Voronoi diagram in linear time, expected or deterministic, augmenting the existing linear-time frameworks for points in convex position with the ability to handle non-point sites and multiple Voronoi faces.
Original language | English |
---|---|
Title of host publication | Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings |
Editors | Khaled Elbassioni, Kazuhisa Makino |
Publisher | Springer Nature |
Pages | 404-414 |
Number of pages | 11 |
ISBN (Print) | 9783662489703 |
DOIs | |
State | Published - 1 Jan 2015 |
Event | 26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan Duration: 9 Dec 2015 → 11 Dec 2015 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9472 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 26th International Symposium on Algorithms and Computation, ISAAC 2015 |
---|---|
Country/Territory | Japan |
City | Nagoya |
Period | 9/12/15 → 11/12/15 |
ID: 38614641