Iterated snap rounding with bounded drift

ABSTRACT

Snap Rounding and its variant, Iterated Snap Rounding, are methods for converting arbitrary-precision arrangements of segments into a fixed-precision representation (we call them SR and ISR for short). Both methods approximate each original segment by a polygonal chain, and both may lead, for certain inputs, to rounded arrangements with undesirable properties: in SR the distance between a vertex and a non-incident edge of the rounded arrangement can be extremely small, inducing potential degeneracies. In ISR, a vertex and a non-incident edge are well separated, but the approximating chain may drift far away from the original segment it approximates. We propose a new variant, Iterated Snap Rounding with Bounded Drift, which overcomes these two shortcomings of the earlier methods. The new solution augments ISR with simple and efficient procedures that guarantee the quality of the geometric approximation of the original segments, while still maintaining the property that a vertex and a non-incident edge in the rounded arrangement are well separated. We investigate the properties of the new method and compare it with the earlier variants. We have implemented the new scheme on top of CGAL, the Computational Geometry Algorithms Library, and report on experimental results.

REFERENCES

• 1: K P Agarwal , Jiri Matousek, Dynamic Half-Space Range Reporting and Its Application, Duke University, Durham, NC, 1991
• 2: The CGAL User Manual, Version 3.1, 2004.
• 3: M. de Berg, D. Halperin, and M. Overmars. An intersection-sensitive algorithm for snap rounding. Technical Report UU-CS 2004-055, Utrecht University, 2004.
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: S. Fortune. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete Comput. Geom., 22(4):593--618, 1999.
• 6: Michael T. Goodrich , Leonidas J. Guibas , John Hershberger , Paul J. Tanenbaum, Snap rounding line segments efficiently in two and three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.284-293, June 04-06, 1997, Nice, France [doi>10.1145/262839.262985]
• 7: D. H. Greene and F. F. Yao. Finite-resolution computational geometry. In Proc. 27th Annu. IEEE Sympos. Found. Comput. Sci., pages 143--152, 1986.
• 8: L. Guibas and D. Marimont. Rounding arrangements dynamically. Internat. J. Comput. Geom. Appl., 8:157--176, 1998.
• 9: Dan Halperin , Eli Packer, Iterated snap rounding, Computational Geometry: Theory and Applications, v.23 n.2, p.209-225, September 2002 [doi>10.1016/S0925-7721(01)00064-5]
• 10: John Hershberger, Improved output-sensitive snap rounding, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137909]
• 11: John D. Hobby, Practical segment intersection with finite precision output, Computational Geometry: Theory and Applications, v.13 n.4, p.199-214, Oct. 1999 [doi>10.1016/S0925-7721(99)00021-8]
• 12: E. Packer. Finite-precision approximation techniques for planar arrangements of line segments. In Master's thesis, Dept. Comput. Sci., Tel-Aviv Univ., 2002.
• 13: S. Raab. Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. M.Sc. thesis, Dept. Comput. Sci., Bar Ilan University, Ramat Gan, Israel, 1999.
• 14: Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
arrangements, finite precision approximation, geometric rounding, line segments, robustness