Covering the Boundary of a Simple Polygon with Geodesic Unit Disks.
作者： Ivo Vigan , George Rabanca
DOI:
关键词: Geodesic 、 Combinatorics 、 Pick's theorem 、 Unit (ring theory) 、 Simple polygon 、 Polygon covering 、 Mathematics 、 Biggest little polygon 、 Boundary (topology)
摘要: We consider the problem of covering boundary a simple polygon on n vertices using minimum number geodesic unit disks. present an O(n \log^2 n+k) time 2-approximation algorithm for finding centers disks, with k denoting found by algorithm.
harvard.edu
arxiv.org参考文章(29)
G.T Toussaint, Computing geodesic properties inside a simple polygon Revue d'intelligence artificielle. ,vol. 3, pp. 9- 42 ,(1989)
Ivo Vigan, Rainer Penninger, Point Set Isolation Using Unit Disks is NP-complete arXiv: Computational Geometry. ,(2013)
Sergey Bereg, David Kirkpatrick, Approximating Barrier Resilience in Wireless Sensor Networks Algorithmic Aspects of Wireless Sensor Networks. ,vol. 5304, pp. 29- 40 ,(2009) , 10.1007/978-3-642-05434-1_5
Magdalene G. Borgelt, Marc van Kreveld, Jun Luo, Geodesic disks and clustering in a simple polygon international symposium on algorithms and computation. pp. 656- 667 ,(2007) , 10.1007/978-3-540-77120-3_57
János Pach, Peter Brass, William Moser, Research Problems in Discrete Geometry ,(2005)
Sergio Cabello, Christian Knauer, Helmut Alt, Panos Giannopoulos, Minimum cell connection and separation in line segment arrangements arXiv: Computational Geometry. ,(2011)
G. Rote, M. Sharir, R. Pollack, Computing the geodesic center of a simple polygon ,(2011)
Sergio Cabello, Panos Giannopoulos, The complexity of separating points in the plane symposium on computational geometry. pp. 379- 386 ,(2013) , 10.1145/2462356.2462383
B. Aronov, On the Geodesic Voronoi Diagram of Point Sites in a Simple Polygon ,(2011)
Adrian Dumitrescu, Csaba D. Tóth, Light orthogonal networks with constant geometric dilation Journal of Discrete Algorithms. ,vol. 7, pp. 112- 129 ,(2009) , 10.1016/J.JDA.2008.07.007