Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1542362.1542402 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
complexity n,log k,geodesic distance,geodesic farthest-site voronoi diagram,farthest-site voronoi diagram,k point site,worst-case complexity,total combinatorial complexity,number h,polygonal domain,voronoi diagram,geodesic,upper bound | Discrete mathematics,Power diagram,Combinatorics,Polygon,Upper and lower bounds,Combinatorial complexity,Diagram,Weighted Voronoi diagram,Voronoi diagram,Geodesic,Mathematics | Conference |
Citations | PageRank | References |
3 | 0.48 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sang Won Bae | 1 | 189 | 31.53 |
| Kyung-Yong Chwa | 2 | 919 | 97.10 |