1989/01/01 by Victor Milenkovic · 3 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #VLSI and FPGA Design Techniques #Rendering (computer graphics) #Grid #Arbitrary-precision arithmetic #Mathematics #Arithmetic #Monotonic function #Floating point #Line segment #Algorithm #Point (geometry) #Computer science #Discrete mathematics #Geometry #Computer graphics (images) #Mathematical analysis
paper · doi:10.1109/sfcs.1989.63525
openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
For the first time it is shown how to reduce the cost of performing specific geometric constructions by using rounded arithmetic instead of exact arithmetic. By exploiting a property of floating-point arithmetic called monotonicity, a technique called double-precision geometry can replace exact arithmetic with rounded arithmetic in any efficient algorithm for computing the set of intersections of a set of lines or line segments. The technique reduces the complexity of any such line or segment arrangement algorithm by a constant factor. In addition, double-precision geometry reduces by a factor of N the complexity of rendering segment arrangements on a 2/sup N/*2/sup N/ integer grid such that output segments have grid points as endpoints.>