Partitioning arrangements of lines I: An efficient deterministic algorithm

1990/10/01 by Pankaj K. Agarwal · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Digital Image Processing Techniques #Discrete mathematics #Efficient algorithm #Geometry #Mathematics #Optimization and Packing Problems #Partition (number theory) #Plane (geometry) #Running time #Set (abstract data type)

paper · pdf · doi:10.1007/bf02187805

crossref issued 1990/10/01 · crossref published 1990/10/01 · crossref published-online 1990/10/01 · crossref published-print 1990/10/01 · openalex publication_date 1990/10/01 · crossref created 2005/09/20 · crossref deposited 2020/04/09 · crossref indexed 2025/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• Construction of ɛ-nets
• A fast las vegas algorithm for triangulating a simple polygon
• An Optimal-Time Algorithm for Slope Selection
• Halfspace range search: An algorithmic application ofk-sets
• Constructing Belts in Two-Dimensional Arrangements with Applications
• On k-Hulls and Related Problems
• Partitioning arrangements of lines II: Applications
• Constructing Arrangements of Lines and Hyperplanes with Applications
• The complexity and construction of many faces in arrangements of lines and of segments

Cited by

• A Practical Algorithm for Enumerating Collinear Points
• K-set (geometry) [wikipedia]