The big sweep : On the power of the wavefront approach to Voronoi diagrams
作者： F. Dehne , R. Klein
DOI: 10.1007/BF02523236
关键词:
摘要: We show that the wavefront approach to Voronoi diagrams (a deterministic line-sweep algorithm does not use geometric transform) can be generalized distance measures more general than Euclidean metric. In fact, we provide first worst-case optimal (O (n logn) time,O(n) space) is valid for full class of what has been callednice metrics in plane. This also solves previously open problem providing anO (nlogn)-time plane-sweep arbitraryL k -metrics. Nice include all convex functions but like Moscow metric, and composed metrics. The conceptually simple, it copes with possible deformations diagram.
springer.com
sci-hub.se 参考文章(19)
Rolf Klein, Abstract Voronoi diagrams and their applications (extended abstract) CG '88 Proceedings of the International Workshop on Computational Geometry on Computational Geometry and its Applications. pp. 148- 157 ,(1988) , 10.1007/3-540-50335-8_31
Rolf Klein, Concrete and Abstract Voronoi Diagrams ,(1989)
Frank Dehne, Rolf Klein, A Sweepcircle Algorithm for Voronoi Diagrams workshop on graph-theoretic concepts in computer science. pp. 59- 83 ,(1987) , 10.1007/3-540-19422-3_5
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
R. Klein, K. Mehlhorn, S. Meiser, On the construction of abstract Voronoi diagrams, II SIGAL '90 Proceedings of the international symposium on Algorithms. pp. 138- 154 ,(1990) , 10.1007/3-540-52921-7_63
Gary M. Shute, Linda L. Deneen, Clark D. Thomborson, AnO(n logn) plane-sweep algorithm forL1 andLź Delaunay triangulations Algorithmica. ,vol. 6, pp. 207- 221 ,(1991) , 10.1007/BF01759042
Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure ACM Computing Surveys. ,vol. 23, pp. 345- 405 ,(1991) , 10.1145/116873.116880
Kevin Q. Brown, Voronoi diagrams from convex hulls Information Processing Letters. ,vol. 9, pp. 223- 228 ,(1979) , 10.1016/0020-0190(79)90074-7
Christian Icking, Rolf Klein, Ngoc-Minh Lê, Lihong Ma, Convex distance functions in 3-space are different Proceedings of the ninth annual symposium on Computational geometry - SCG '93. pp. 116- 123 ,(1993) , 10.1145/160985.161007
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