Forest-like abstract Voronoi diagrams in linear time

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Abstract Voronoi diagrams

Forest structures

General distance

Linear-time algorithms

Voronoi diagrams

Publikations- och innehållstyp

art (ämneskategori)

ref (ämneskategori)