Voronoi diagrams for convex polygon-offset distance functions
作者： G. Barequet , M. T. Dickerson , M. T. Goodrich
关键词: Offset distance 、 Convex polygon 、 Combinatorics 、 Weighted Voronoi diagram 、 Mathematics 、 Offset (computer science) 、 Voronoi diagram 、 Centroidal Voronoi tessellation 、 Power diagram
摘要: In this paper we develop the concept of a convexpolygon-offset distance function. Using offset as notion distance, show how to compute corresponding nearest- and furthest-site Voronoi diagrams point sites in plane. We provide near-optimal deterministicO(n(logn + log2m) +m)-time algorithms, wheren is number points andm complexity underlying polygon, for computing compact representations both diagrams.
springer.com
sci-hub.se 参考文章(17)
Oswin Aichholzer, Franz Aurenhammer, David Alberts, Bernd Gärtner, A Novel Type of Skeleton for Polygons Journal of Universal Computer Science. ,vol. 1, pp. 752- 761 ,(1996) , 10.1007/978-3-642-80350-5_65
David Rappaport, Computing the Furthest Site Voronoi Diagram for a Set of Discs (Preliminary Report) workshop on algorithms and data structures. pp. 57- 66 ,(1989) , 10.1007/3-540-51542-9_7
Rolf Klein, Derick Wood, Voronoi Diagrams Based on General Metrics in the Plane symposium on theoretical aspects of computer science. pp. 281- 291 ,(1988) , 10.1007/BFB0035852
Oswin Aichholzer, Franz Aurenhammer, Straight skeletons for general polygonal figures in the plane Lecture Notes in Computer Science. pp. 117- 126 ,(1996) , 10.1007/3-540-61332-3_144
Rolf Klein, Kurt Mehlhorn, Stefan Meiser, Randomized incremental construction of abstract Voronoi diagrams Computational Geometry: Theory and Applications. ,vol. 3, pp. 157- 184 ,(1993) , 10.1016/0925-7721(93)90033-3
Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Michael T. Goodrich, Offset-polygon annulus placement problems Computational Geometry: Theory and Applications. ,vol. 47, pp. 125- 141 ,(1998) , 10.1016/S0925-7721(98)00025-X
L. Paul Chew, Robert L. (Scot) Dyrsdale, Voronoi diagrams based on convex distance functions symposium on computational geometry. pp. 235- 244 ,(1985) , 10.1145/323233.323264
M. McAllister, D. Kirkpatrick, J. Snoeyink, A compact piecewise-linear voronoi diagram for convex sites in the plane Discrete and Computational Geometry. ,vol. 15, pp. 73- 105 ,(1996) , 10.1007/BF02716580
Saad T. Bakir, Tolerance Design: A Handbook for Developing Optimal Specifications ,(1996)
K. Mehlhorn, St. Meiser, C. Ó'Dúnlaing, On the construction of abstract voronoi diagrams Discrete & Computational Geometry. ,vol. 6, pp. 211- 224 ,(1991) , 10.1007/BF02574686