TY - GEN
T1 - Optimal algorithm for intersecting line segments in the plane
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1988
Y1 - 1988
N2 - The authors present the first optimal algorithm for the following problem: given n line segments in the plane, computes 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.
AB - The authors present the first optimal algorithm for the following problem: given n line segments in the plane, computes 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.
UR - http://www.scopus.com/inward/record.url?scp=0024140066&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024140066&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1988.21975
DO - 10.1109/sfcs.1988.21975
M3 - Conference contribution
AN - SCOPUS:0024140066
SN - 0818608773
SN - 9780818608773
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 590
EP - 600
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - Publ by IEEE
ER -