Close this search box.

Robustness and Precision in Geometric Computing, Seminar, Fall 2001–2002



Lecture: Wednesday, 16:00–18:00, Schreiber 309 <- note change of room

Instructor: Dan Halperin
Office hours: Wednesday, 15:00–16:00, Schreiber 219

Implementing algorithms for solving geometric problems (like computing the convex hull of a set of points, constructing Voronoi diagrams, planning collision-free paths for robots) turns out to be extremely difficult. These difficulties have for a long time prevented the development of robust and reliable geometric software.

Considerable progress in solving these problems has been made in recent years and in the seminar we will cover some such developments including rounding schemes for planar maps, extensions of the standard computer number types (such as arbitrary precision rationals) and software libraries that support these extensions, and perturbation schemes to remove degeneracies from geometric input.

After two introductory meetings, we will follow the outline below of students presentations (temporary list, stay tuned).

Introduction I (D.H.)

Geometric computing, arithmetic precision and degeneracies, survey of the papers that will be presented in the seminar

Survey papers:

  1. Robustness and precision issues in geometric computation
    Schirra, Chapter 14 in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (editors), North Holland, 2000
  2. Robust Geometric Computation
    Yap, Chapter 35 in Handbook of Discrete and Computational Geometry, J.E. Goodman and J. O’Rourke (editors), CRC Press LLC, Boca Raton, FL, 1997
  3. Robust geometric computing [psz]
    Halperin, to appear in International journal of Robotics Reserach
    An abridged version appeared in Algorithmic Foundations of Robotics (WAFR), B.R. Donald, K.M. Lynch, and D. (editors), A.K. Peters, 9–22, 2000

Introduction II (D.H.)

  • A few basic algorithms and data structures in computational geometry related to maps and arrangements

Snap rounding I

  • Practical segment intersection with finite precision output
    Hobby, Computational Geometry: Theory and Applications , 13:199–214 (1999)
  • Rounding Arrangements Dynamically
    Guibas and Marimont, International Journal Computational Geometry & Applications 8:157–176 (1998)

Slides of the presentation by Shai Hirsch [ppt]

Snap rounding II

  • Iterated snap rounding [psz]
    Halperin and Packer
  • Snap Rounding Line Segments Efficiently in Two and Three Dimension (The 2D part)
    Goodrich, Guibas, Hershberger, Tanenbaum, Proceedings of the 13th Annual ACM Symposium Computational Geometry 284–293 (1997)

Slides of the presentation by Mark Waitser [ppt]

  • What every computer scientist should know about floating-point arithmetic, David Goldberg, ACM Computing Surveys 32(1):5–48 (1991)

Additional material:

  • IEEE Standard 754-1985 for binary floating-point arithmetic, SIGPLAN 22:9-25, 1987
  • Computer Arithmetic
    David Goldberg, Appendix A of Computer Architecture, a Quantitative Approach by Hennessy and Patterson, 2nd Edition, Morgan Kaufman

Slides of the presentation by Ami Peled [ppt]

LEDA: Overview, number types and geometry kernels

  • The LEDA book (by Mehlhorn and Naeher), overview + sections 4.1–4.3, 9.1–9.5, 9.9

Slides of the presentation by Mark Gilerovich: README first [txt], leda (the presentation) [zip], examples [tgz]

Floating Point Filters

  • The LEDA book, sections 9.6-9.8

Additional material:

  • Static analysis yields efficient exact integer arithmetic for computational geometry
    Fortune and Van Wyck, ACM Transactions on Graphics , 15(3): 223–248 (1996)
  • Adaptive robust floating-point arithmetic and fast robust geometric predicates
    J.R. Shewchuk, Discrete and Computational Geometry 18: 305–363 (1997)

Algebraic numbers I: Theory

  • A strong and easily computable separation bound for arithmetic expressions involving radicals
  • Burnikel, Fleischer, Mehlhorn, Schirra, Algorithmica 27: 87–99 (2000)

Additional material:

  • A new constructive root bound for algebraic expressions
    Li and Yap, (SODA) 2001
  • A separation bound for real algebraic expressions
    Burnikel, Funke, Mehlhorn, Schirra, Schmitt, (ESA) 2001

Slides (ppt) of the presentation by Eduard Oks [ppt]

Algebraic numbers II: Practice

  • LEDA real (section 4.4 in The LEDA book) and CORE Expr

Slides of the presentation by Ron Wein [ppt]

CGAL: Overview, geometry kernels, maps and arrangements

  • On the design of CGAL, a Computational Geometry Algorithms Library
    Fabri, Giezeman, Kettner, Schirra, Schönherr, Software—Practice and Experience 30:1167–1202 (2000)
  • The design and implementation of planar maps in CGAL
    Flato, Halperin, Hanniel, Nechushtan, Ezra
    The full version [psz]
    A preliminary version appeared in Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE) London, 1999, Springer LNCS Vol. 1668, 154–168
  • Robust geometric computing in motion [psz]
    Halperin, to appear in International Journal of Robotics Reserach

Symbolic perturbations

  • Efficient perturbations for handling geometric degeneracies
    Emiris, Canny and Seidel, Algorithmica 19:219-242 (1997)

Additional material:

  • Simulation of Simplicity
    Edelsbrunner and Muecke, ACM Transactions on Graphics 9:66-104,, 1990
  • Symbolic treatment of geometric degeneracies
    Yap, Journal of Symbolic Computing 10:349–370, 1990
  • The nature and meaning of perturbations in geometric computing
    Seidel, Discrete and Computational Geometry 19: 1-17, 1998

Slides of the presentation by Moshe Chikurel [ppt]

Controlled perturbation

  • A perturbation scheme for spherical arrangements with application to molecular modeling
    Halperin and Shelton, Computational Geometry: Theory and Applications 10:273–288, 1998

Additional material:

  • Spheres, molecules, and hidden surface removal
    Halperin and Overmars, Computational Geometry: Theory and Applications 11:83–102, 1998
  • Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes
    Raab, M.Sc. Thesis, Tel Aviv University and Bar Ilan, 1999

Yair Oz - Webcreator


Skip to content