A note on visibility-constrained Voronoi diagrams (Q400517)

The authors introduce \textit{baseline Voronoi diagrams} as follows. Given are finitely many points \(p_1,\dots,p_n\) in the Euclidean plane \(\mathbb R^2\) and closed halfspaces \(H_1,\dots,H_n\) of \(\mathbb R^2\) such that, for each \(i\), the point \(p_i\) belongs to the boundary of \(H_i\). A point \(p_i\) is said to see a point \(x\) of \(\mathbb R^2\) if \(x\) lies in \(H_i\) and, for every \(j \in \{1,\dots,n\}\setminus \{i\}\), the segment joining \(p_i\) and \(x\) does not intersect the boundary of \(H_j\). With each \(p_i\) one associates the set \(\mathrm{reg}(p_i)\) of all points \(x\) seen by \(p_i\) and such that no point \(p_j\) with \(j \in \{1,\dots,n\} \setminus \{i\}\) that sees \(x\) is closer to \(x\). The baseline Voronoi diagram for the data \(p_1,\dots,p_n\), \(H_1,\dots,H_n\) is composed of the regions \(\mathrm{reg}(p_1),\dots,\mathrm{reg}(p_n)\). The union of the boundaries of the latter regions can be viewed as plane graph (with edges being line segments) so that one can speak (using the standard terminology for plane graphs) about vertices, edges and faces of baseline Voronoi diagrams.NEWLINENEWLINEThe main result of the paper asserts that the baseline Voronoi diagram for \(n\) points has \(O(n)\) faces and \(O(n^{4/3})\) edges and vertices.