|
|||||
|
|
Farthest-polygon Voronoi diagrams |
|
| Authors: | Otfried Cheong Samuel Hornus Sylvain Lazard |
| Institution: | a Dept. of Computer Science, KAIST, Daejeon, Republic of Korea b Université Nancy 2, LORIA, Nancy, France c INRIA Saclay - Île-de-France, Orsay, France d National ICT Australia Ltd., Sydney, Australia e INRIA Nancy Grand-Est, LORIA, Nancy, France f School of Computing, Soongsil University, Seoul, Republic of Korea |
| Abstract: | Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog3n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region. |
| Keywords: | Voronoi diagram |
| 本文献已被 ScienceDirect 等数据库收录！ | |