### An optimal algorithm for intersecting line segments in the planeAn optimal algorithm for intersecting line segments in the plane

Access Restriction
Subscribed

 Author Chazelle, Bernard ♦ Edelsbrunner, Herbert Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The main contribution of this work is an $\textit{O}(\textit{n}$ log $\textit{n}$ + $\textit{k})-time$ algorithm for computing all $\textit{k}$ intersections among $\textit{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 $\textit{n}$ + $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-01-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 1 Page Count 54 Starting Page 1 Ending Page 54

#### Open content in new tab

Source: ACM Digital Library