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 -