Robustness and Precision in Geometric Computing

Seminar, Fall 2001-02

0368410801

Instructor: Dan Halperin

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

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:
- Schirra, Robustness and precision issues in geometric computation, Chapter 14 in Handbook of Computational Geometry , J.-R. Sack and J. Urrutia (editors), North Holland, 2000.
- Yap, Robust Geometric Computation, Chapter 35 in Handbook of Discrete and Computational Geometry , J.E. Goodman and J. O'Rourke (editors), CRC Press LLC, Boca Raton, FL, 1997.
- Halperin, Robust geometric computing in motion , to appear in International journal of Robotics Reserach. An abridged version appeared in Algorithmic Foundations of Robotics (WAFR2000) , 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
- Hobby, Practical segment intersection with finite precision output, Computational Geometry: Theory and Applications , 13:199-214 (1999)
- Guibas and Marimont, Rounding Arrangements Dynamically, Internat. J. Comput. Geom. Appl. 8:157-176 (1998)

Slides (ppt XP) of the presentation by Shai Hirsch.

 Snap rounding II
- Halperin and Packer, Iterated snap rounding
- Goodrich, Guibas, Hershberger, Tanenbaum, Snap Rounding Line Segments Efficiently in Two and Three Dimension (The 2D part), Proc. 13th Annu. ACM Sympos. Comput. Geom. 284-293 (1997)

Slides of the presentation by Mark Waitser.

 "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" by David Goldberg, Appendix A of Computer Architecture, a Quantitative Approach by Hennessy and Patterson, 2nd Edition, Morgan Kaufman.

Slides (ppt) of the presentation by Ami Peled.

 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 , leda.zip (the presentation) , examples.tar.gz

 Floating Point Filters
The LEDA book, sections 9.6-9.8

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

 Algebraic numbers I: Theory
Burnikel, Fleischer, Mehlhorn, Schirra, A strong and easily computable separation bound for arithmetic expressions involving radicals, Algorithmica 27: 87-99 (2000)

Additional material:
- Li and Yap, A new constructive root bound for algebraic expressions (SODA '01)
- Burnikel, Funke, Mehlhorn, Schirra, Schmitt, A separation bound for real algebraic expressions (ESA '01)

Slides (ppt) of the presentation by Eduard Oks.

 Algebraic numbers II: Practice
LEDA real (section 4.4 in the LEDA book) and CORE Expr

Slides (ppt, Office 2000) of the presentation by Ron Wein

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

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

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

Slides (ppt) of the presentation by Moshe Chikurel

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

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