Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Forest-like abstract Voronoi diagrams in linear time

Bohler, Cecilia ; Klein, Rolf ; Lingas, Andrzej LU and Liu, Chih Hung (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:
author
; ; and
organization
publishing date
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
2025-10-14 13:09:16
@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}},
}