The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
Sang Won Bae, Kyung‐Yong Chwa · 2009
We investigate the farthest-site Voronoi diagram of k point sites with respect to the geodesic distance in a polygonal domain of n corners and h (≥ 0) holes. In the case of h=0, Aronov et al. [2] in 1993 proved that there are at most O(k) faces in the diagram and the complexity of the diagram is at most O(n+k). However, any nontrivial upper bound on the geodesic farthest-site Voronoi diagram in a polygonal domain when h > 0 remains unknown afterwards. In this paper, we show that the diagram in a polygonal domain consists of Θ(hk) faces and its total combinatorial complexity is Θ(nk) in the worst case for any h ≥ 1. Interestingly, the worst-case complexity of the diagram is independent from the number h of holes if h ≥ 1 while the maximum possible number of faces is dependent on h rather than on the complexity n of the polygonal domain. Also, we present an O(nk log2(n+k) log k)-time algorithm that constructs the diagram explicitly.