Numerical stability of algorithms for line arrangements

1991/01/01 by Steven Fortune, Victor Milenkovic · 2 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Citation #Computer science #Algorithm #Line (geometry) #Stability (learning theory) #Operations research #Library science #Mathematics #Machine learning

paper · pdf · doi:10.1145/109648.109685

openalex publication_date 1991/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We analyze the behavior of two line arrangement algorithms, a sweepline algorithm and an incremental algorithm, in approximate arithmetic.

Citations

• Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic
• Primitives for the manipulation of general subdivisions and the computation of Voronoi

Cited by

• Allowable Sequences and Order Types in Discrete and Computational Geometry
• Arrangement of lines [wikipedia]