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

Seminar

0368410801

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 13^th 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, 2^nd 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 3^rd 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