Forest-like abstract Voronoi diagrams in linear time
(2018) In Computational Geometry: Theory and Applications 68. p.134-145- Abstract
Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S'⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V(S) inside D can be constructed in linear time.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/875ae243-5408-43fa-8af7-92678053d679
- author
- Bohler, Cecilia ; Klein, Rolf ; Lingas, Andrzej LU and Liu, Chih Hung
- organization
- publishing date
- 2018-03
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Abstract Voronoi diagrams, Forest structures, General distance, Linear-time algorithms, Voronoi diagrams
- in
- Computational Geometry: Theory and Applications
- volume
- 68
- pages
- 134 - 145
- publisher
- Elsevier
- external identifiers
-
- scopus:85023625891
- wos:000415778300011
- ISSN
- 0925-7721
- DOI
- 10.1016/j.comgeo.2017.06.013
- language
- English
- LU publication?
- yes
- id
- 875ae243-5408-43fa-8af7-92678053d679
- date added to LUP
- 2017-07-27 14:25:23
- date last changed
- 2024-08-19 02:08:20
@article{875ae243-5408-43fa-8af7-92678053d679, abstract = {{<p>Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S'⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V(S) inside D can be constructed in linear time.</p>}}, author = {{Bohler, Cecilia and Klein, Rolf and Lingas, Andrzej and Liu, Chih Hung}}, issn = {{0925-7721}}, keywords = {{Abstract Voronoi diagrams; Forest structures; General distance; Linear-time algorithms; Voronoi diagrams}}, language = {{eng}}, pages = {{134--145}}, publisher = {{Elsevier}}, series = {{Computational Geometry: Theory and Applications}}, title = {{Forest-like abstract Voronoi diagrams in linear time}}, url = {{http://dx.doi.org/10.1016/j.comgeo.2017.06.013}}, doi = {{10.1016/j.comgeo.2017.06.013}}, volume = {{68}}, year = {{2018}}, }