Efficient computation of continuous skeletons
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 18-27
- https://doi.org/10.1109/sfcs.1979.15
Abstract
An O(n lgn) algorithm is presented for the construction of skeletons of arbitrary n-line polygonal figures. This algorithm is based on an O(n lgn) algorithm for the construction of generalized Voronoi diagrams (our generalization replaces point sets by sets of line segments constrained to intersect only at end points). The generalized Voronoi diagram algorithm employs a linear time algorithm for the merging of two arbitrary (standard) Voronoi diagrams.Keywords
This publication has 9 references indexed in Scilit:
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning TreesJournal of the ACM, 1979
- Computing Dirichlet Tessellations in the PlaneThe Computer Journal, 1978
- Finding Minimum Spanning TreesSIAM Journal on Computing, 1976
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Geometric complexityPublished by Association for Computing Machinery (ACM) ,1975
- Continuous Skeletons from Digitized ImagesJournal of the ACM, 1969
- A Method for Obtaining Skeletons Using a Quasi-Euclidean DistanceJournal of the ACM, 1968
- Shape Recognition, Prairie Fires, Convex Deficiencies and SkeletonsThe American Mathematical Monthly, 1968
- Computer representation of planar regions by their skeletonsCommunications of the ACM, 1967