Su, Bing; Xu, Yinfeng; Zhu, Binhai Baseline bounded half-plane Voronoi diagram. (English) Zbl 1276.68166 Discrete Math. Algorithms Appl. 5, No. 3, Article ID 1350021, 7 p. (2013). 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. Cited in 1 Document MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:half-plane; baseline; Voronoi diagram PDFBibTeX XMLCite \textit{B. Su} et al., Discrete Math. Algorithms Appl. 5, No. 3, Article ID 1350021, 7 p. (2013; Zbl 1276.68166) 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.