Name
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(nlog^3n) 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.comgeo.2010.11.004 | european symposium on algorithms |
Keywords | DocType | Volume |
farthest-polygon voronoi diagram,total complexity n,voronoi region,entire region,farthest-site voronoi diagram,closest point,k-1 connected component,k disjoint,general position,polygonal site,structural property,voronoi diagram,connected component | Journal | 44 |
Issue | ISSN | ISBN |
4 | Computational Geometry: Theory and Applications | 3-540-75519-5 |
Citations | PageRank | References |
23 | 1.18 | 12 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Otfried Cheong | 1 | 594 | 60.27 |
| Hazel Everett | 2 | 296 | 29.68 |
| marc glisse | 3 | 267 | 24.05 |
| Joachim Gudmundsson | 4 | 1362 | 100.81 |
| Samuel Hornus | 5 | 166 | 12.52 |
| Sylvain Lazard | 6 | 531 | 53.78 |
| Mira Lee | 7 | 105 | 8.06 |
| Hyeon-suk Na | 8 | 183 | 17.53 |