Computing Many Faces in Arrangements of Lines and Segments

1998/04/01 by Pankaj K. Agarwal, Jiřı́ Matoušek, Otfried Schwarzkopf · 48 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs #Data Management and Algorithms #Combinatorics #Randomized algorithm #Simple (philosophy) #Efficient algorithm #Mathematics #Computer science #Algorithm #Discrete mathematics

paper · open access · doi:10.1137/s009753979426616x

published in SIAM Journal on Computing 27(2), 491-505 (Society for Industrial and Applied Mathematics)

openalex publication_date 1998/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(n log n) expected time algorithm for computing √(n) cells in an arrangement of n lines.

Citations

• Combinatorial complexity bounds for arrangements of curves and spheres
• A theorem on arrangements of lines in the plane
• Partitioning arrangements of lines II: Applications

Cited by

• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Arrangement of lines [wikipedia]