---
res:
bibo_abstract:
- The main contribution of this work is an O(n log n + k)-time algorithm for computing
all k intersections among n line segments in the plane. This time complexity is
easily shown to be optimal. Within the same asymptotic cost, our algorithm can
also construct the subdivision of the plane defined by the segments and compute
which segment (if any) lies right above (or below) each intersection and each
endpoint. The algorithm has been implemented and performs very well. The storage
requirement is on the order of n + k in the worst case, but it is considerably
lower in practice. To analyze the complexity of the algorithm, an amortization
argument based on a new combinatorial theorem on line arrangements is used.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Bernard
foaf_name: Chazelle, Bernard
foaf_surname: Chazelle
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
bibo_doi: 10.1145/147508.147511
bibo_issue: '1'
bibo_volume: 39
dct_date: 1992^xs_gYear
dct_publisher: ACM@
dct_title: An optimal algorithm for intersecting line segments in the plane@
...