×

Baseline bounded half-plane Voronoi diagram. (English) Zbl 1276.68166

Summary: Let \(P=\{p_{1}, p_{2},\dots, p_{n}\}\) be a set of points in the Euclidean plane with each point \(p_{i}\) being associated with a given direction \(v_{i} \in V\). \(P(p_{i}, v_{i})\) defines a half-plane and \(L(p_{i}, v_{i})\) denotes the baseline that is perpendicular to \(v_{i}\) and passing through \(p_{i}\). Define a region dominated by \(p_{i}\) and \(v_{i}\) as a baseline bounded half-plane Voronoi region, denoted as \(\mathrm{Vor}(p_{i}, v_{i})\), if a point \(x \in \mathrm{Vor}(p_{i}, v_{i})\), then (1) \(x \in P(p_{i}, v_{i})\); (2) the line segment \(l(x, p_{i})\) does not cross any baseline; (3) if there is a point \(p_{j}\), such that \(x \in P(p_{j}, v_{j})\), and the line segment \(l(x, p_{j})\) does not cross any baseline then \(d(x, p_{i}) \leq d(x, p_{j})\), \(j\neq i\). The baseline bounded half-plane Voronoi diagram, denoted as \(\mathrm{Vor}(P,V)\), is the union of all \(\mathrm{Vor}(p_{i}, v_{i})\). We show that \(\mathrm{Vor}(p_{i},v_{i})\) and \(\mathrm{Vor}(P,V)\) can be computed in \(O(n \log n)\) and \(O(n^{2}\log n)\) time, respectively. For the heterogeneous point set, the same problem is also considered.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1145/116873.116880 · doi:10.1145/116873.116880
[2] DOI: 10.1007/978-1-4612-1098-6 · doi:10.1007/978-1-4612-1098-6
[3] Voronoi G. M., J. Reine Angew. Math. 134 pp 198– (1908)
[4] DOI: 10.1016/j.comgeo.2005.07.002 · Zbl 1113.65019 · doi:10.1016/j.comgeo.2005.07.002
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.