AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments
Tóm tắt
LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.
Tài liệu tham khảo
F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane,Pattern Recognition 17 (1984), 251–257.
B. S. Baker, S. J. Fortune, and E. H. Grosse, Stable prehension with three fingers,Proceedings of the 17th ACM Symposium on Theory of Computing, 1984.
C. Borgers, C. Peskin, and O. Widlund, Private communication, 1984.
L. P. Chew and R. L. Drysdale, Voronoi diagrams based on convex distance functions,Proceedings of the ACM Symposium on Computational Geometry, 235–244, 1985.
R. L. Drysdale III, Generalized Voronoi Diagrams and Geometric Searching, Computer Science Technical Report STAN-CS-79-705, Stanford University, Stanford, California, 1979.
S. Fortune, A fast algorithm for polygon containment by translation,Proceedings of the 12th International Colloquium on Automata, Language, and Programming, 189–198, 1985.
S. Fortune, A sweepline algorithm for Voronoi diagrams,Proceedings of the Second ACM Symposium on Computational Geometry, 313–322, 1986.
H. Imai, M. Iri, and K. Murota, Voronoi diagram in the Laguerre geometry and its applications,SIAM J. Comput. 14 (1985), 93–105.
D. G. Kirkpatrick, Efficient computation of continuous skeletons,Proceedings of the 14th IEEE Symposium on Foundations of Computer Science 18–27, 1979.
D. G. Kirkpatrick, Private communication, 1984.
D. T. Lee, Two-dimensional Voronoi diagram in theL p -metric,J. Assoc. Comput. Mach. 27 (1980), 604–618.
D. T. Lee, Medial axis transformation of a planar shape,IEEE Trans. Pattern Anal. Mach. Intel. 4 (1982), 363–369.
D. T. Lee and R. L. Drysdale III, Generalization of Voronoi diagrams in the plane,SIAM J. Comput. 10 (1981), 73–87.
D. T. Lee and C. K. Wong, Voronoi diagrams inL 1(L ∞) metrics with two-dimensional storagè applications,SIAM J. Comput. 9 (1980), 200–211.
D. Leven and M. Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams,J. Discrete Comput. Geom. 2 (1987), 9–31.
D. Leven and M. Sharir, Intersection problems and applications of Voronoi diagrams, inAdvances in Robotics, Vol. 1 (J. Schwartz and C. K. Yap, eds.), Erlbaum, 1987.
H. P. Moravec,Robot Rover Visual Navigation, UMI Research Press, 1981. (Ph.D. thesis, Stanford.)
C. Ó'Dúnlaing and C. K. Yap, A retraction method for planning the motion of a disc,J. Algorithms 6 (1985) 104–111. Also inPlanning, Geometry, and Complexity (J. Hopcroft, J. Schwartz and M. Sharir, eds.), Ablex, Norwood, NJ, 1987).
C. Ó'Dúnlaing, M. Sharir, and C. K. Yap, Retraction: a new approach to motion planning,Proceedings of the 15th IEEE Symposium on Foundations of Computer Science, 207–220, 1983. Also inPlanning, Geometry, and complexity (J. Hopcroft, J. Schwartz and M. Sharir, eds.), Ablex, Norwood, NJ, 1987).
C. Ó'Dúnlaing, M. Sharir, and C. K. Yap, Generalized Voronoi diagrams for moving a ladder: I. Topological analysis,Comm. Pure Appl. Math. XXXIX (1986), 423–483.
C. Ó'Dúnlaing, M. Sharir, and C. K. Yap, Generalized Voronoi diagrams for moving a ladder: II. Efficient construction of the diagram,Algorithmica 2 (1987), 27–59.
F. P. Preparata, The medial axis of a simple polygon,Proceedings of the Sixth Symposiums on Mathematical Foundations of Computer Science, 443–450, 1977.
R. Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, M. Sc. thesis, University of British Columbia, 1981.
M. I. Shamos and D. Hoey, Closest point problems,Proceedings of the 16th IEEE Symposium on Foundations of Computer Science, 151–162, 1975.
M. Sharir, Intersection and closest-pair problems for a set of circular discs,SIAM J. Comput. 14 (1985), 448–468.
C. K. Yap, AnO(n logn) Algorithm for the Voronoi Diagram of a Set of Simple Curve Segments, Robotics Laboratory Report No. 43, Courant Institute, New York University, New York, 1985.