A note on visibility-constrained Voronoi diagrams

F. Aurenhammer, B. Su, Y.-F. Xu, and B. Zhu

Abstract:

We consider a variant of visibility-constrained Voronoi diagrams for $n$ given point sites in the Euclidean plane. Whereas such diagrams typically are of size $\Omega(n^2)$, the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in $n$.



Reference: F. Aurenhammer, B. Su, Y.-F. Xu, and B. Zhu. A note on visibility-constrained Voronoi diagrams. Discrete Applied Mathematics, 174:52-56, 2014.