Title :
An optimal algorithm for intersecting line segments in the plane
Author :
Chazelle, Bernard ; Edelsbrunner, Herbert
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
The authors present the first optimal algorithm for the following problem: given n line segments in the plane, compute all k pairwise intersections in O(n log n+k) time. Within the same asymptotic cost the algorithm will also compute the adjacencies of the planar subdivision induced by the segments, which is a useful data structure for contour-filling on raster devices
Keywords :
computational complexity; computational geometry; adjacencies; asymptotic cost; contour-filling; data structure; intersecting line segments; optimal algorithm; pairwise intersections; planar subdivision; plane; raster devices; Algorithm design and analysis; Computer graphics; Computer science; Costs; Data structures; Image segmentation; Independent component analysis; Processor scheduling; Robots; Solid modeling;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21975
