Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 500-505
- https://doi.org/10.1109/sfcs.1989.63525
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Calculating approximate curve arrangements using rounded arithmeticPublished by Association for Computing Machinery (ACM) ,1989
- Stable maintenance of point set triangulations in two dimensionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Verifiable implementations of geometric algorithms using finite precision arithmeticArtificial Intelligence, 1988
- An optimal algorithm for intersecting line segments in the planePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A fast planar partition algorithm. IPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Finite-resolution computational geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Linear time algorithms for visibility and shortest path problems inside simple polygonsPublished by Association for Computing Machinery (ACM) ,1986
- Constructing arrangements of lines and hyperplanes with applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- High-Level Language Implications of the Proposed IEEE Floating-Point StandardACM Transactions on Programming Languages and Systems, 1982
- Arrangements and SpreadsCBMS Regional Conference Series in Mathematics, 1972