### 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:

**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**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- 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*284–293 (1997)^{th}Annual ACM Symposium Computational Geometry

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*London, 1999, Springer LNCS Vol. 1668, 154–168^{rd}International Workshop on Algorithm Engineering (WAE)- 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