Seminar, Fall 2001-02

- 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.