Loading...
Please wait, while we are loading the content...
Similar Documents
Farthest-polygon voronoi diagrams∗ (2010).
| Content Provider | CiteSeerX |
|---|---|
| Author | Cheong, Otfried Everett, Hazel Glisse, Marc Gudmundsson, Joachim Hornus, Samuel Lazard, Sylvain Lee, Mira Na, Hyeon-Suk |
| 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(n log3 n) 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. 1 |
| File Format | |
| Publisher Date | 2010-01-01 |
| Access Restriction | Open |
| Subject Keyword | Farthest-polygon Voronoi Diagram Polygonal Site Structural Property General Position Entire Region Connected Component Time Algorithm Farthest-site Voronoi Diagram Voronoi Region Total Complexity Closest Point |
| Content Type | Text |
