×

Abstract Voronoi diagrams with disconnected regions. (English) Zbl 1331.68243

Summary: Abstract Voronoi diagrams, AVDs for short, are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and distance. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD axioms, structural results and efficient algorithms become available without further effort; for example, the first optimal algorithms for constructing nearest Voronoi diagrams of disjoint convex objects, or of line segments under the Hausdorff metric, have been obtained this way. One of these axioms stated that all Voronoi regions must be pathwise connected, a property quite useful in divide & conquer and randomized incremental construction algorithms. Yet, there are concrete Voronoi diagrams where this axiom fails to hold.
In this paper we consider, for the first time, abstract Voronoi diagrams with disconnected regions. By combining a randomized incremental construction technique with trapezoidal decomposition we obtain an algorithm that runs in expected time \(O(s^2 n \sum\nolimits_{j=3}^n m_j/j)\), where \(s\) is the maximum number of faces a Voronoi region in a subdiagram of three sites can have, and where \(m_{j}\) denotes the average number of faces per region in any subdiagram of \(j\) sites. In the connected case, where \(s = 1 = m_{j}\), this results in the known optimal bound \(O(n \sum\nolimits_{j=3}^n 1/j) = O(n\log n)\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1145/116873.116880 · doi:10.1145/116873.116880
[2] DOI: 10.1016/j.comgeo.2009.03.002 · Zbl 1173.65014 · doi:10.1016/j.comgeo.2009.03.002
[3] DOI: 10.1007/BF02574686 · Zbl 0723.68048 · doi:10.1007/BF02574686
[4] DOI: 10.1016/0925-7721(93)90033-3 · Zbl 0797.68153 · doi:10.1016/0925-7721(93)90033-3
[5] DOI: 10.1016/S0925-7721(02)00167-0 · Zbl 1027.65026 · doi:10.1016/S0925-7721(02)00167-0
[6] DOI: 10.1007/s00454-003-2947-0 · Zbl 1159.68614 · doi:10.1007/s00454-003-2947-0
[7] DOI: 10.1142/S0218195906001963 · Zbl 1122.52007 · doi:10.1142/S0218195906001963
[8] Karavelas M. I., LNCS 2832 pp 337– (2003)
[9] DOI: 10.1142/S0218195901000663 · Zbl 1074.68643 · doi:10.1142/S0218195901000663
[10] DOI: 10.1016/0925-7721(91)90012-4 · Zbl 0733.68092 · doi:10.1016/0925-7721(91)90012-4
[11] DOI: 10.1016/0925-7721(93)90009-U · Zbl 0781.68112 · doi:10.1016/0925-7721(93)90009-U
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.