**0368.4073.0**

**Lecture**: Monday 16:00–19:00, Schreiber 6

**Instructor**: Dan Halperin

**Office hours**: Wednesday, 16:00–17:00, Schreiber 114

Teaching Assistant: Eti Ezra, [email protected]

Assignments: instructions, program fragments, input files

The final assignment and oral exam [psz]

The course will cover geometric-computing techniques that are useful in solving problems in a variety of application domains including robotics, computer-aided design and manufacturing, GIS and more. The emphasis will be on practical solutions. Among the topics of the course: geometric arrangements and their applications; configuration space and robot motion planning; movable separability and assembly planning for multi-part objects. In addition we will address robustness issues in geometric software, data types for exact computing, and handling of degenerate input.

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.

Prerequisites: software1, data structures, and a course on algorithms. Knowledge of C++ would help.

Having taken the course Computational Geometry is an advantage but not a requirement.

The final grade will be determined by: 80% homework assignments including one large-scale assignment, and 20% oral exam.

### Course summary

**21.02.2000**Introduction- Motivating problems: object placement and compaction, robot motion planning, part orienting, mechanical assembly planning, visibility
- From problems to solutions: formulating the problem in a convenient `configuration space’, combinatorial analysis, representation/data structures, algorithms, implementation
- Example: aspects graphs of a convex polygon in parallel and perspective projections, the circle of directions, arrangements of lines
- See references to books and surveys on arrangements in the course bibliography

**28.02.2000**Minkowski sums- Motivating problems: object placement, robot motion planning, tolerance and offset
- The connection between motion planning and Minkowski sums
- Minkowski sum of two convex polygons: properties and algorithm
- Arrangements of segments, constraint curves, upper bound on the complexity of Minkowski sums of general polygonal sets
- Minkowski sum of a convex and general polygon; to be continued
- Most of the material is taken from the book by de Berg et al. (see the course bibliography ), Chapter 13

Assignment no. 1 [psz], due: March 20th, 2000

frame programs, example input files

**06.03.2000**Minkowski sums, cont’d- Minkowski sum of a convex \(m\)-gon and general \(n\)-gon: proof of the tight complexity bound \(O(mn)\) of the free space
- Introduction to lower envelopes
- background material for those who did not take the course computational geometry: representing 2D maps—DCEL and vertical decomposition, a quick review of the seep line algorithm for detecting the intersection of segments in the plane
- Most of the material is taken from the book by de Berg et al. (see the course bibliography)

The Minkowski sum bound appears in Chapter 13 in the book.

The background material appears in Chapter 2

**09.03.2000**Talks on the CGAL project and library- Mariette Yvinec: Triangulations in CGAL
- Stefan Schirra: Precision and Robustness in CGAL
- Much material about CGAL can be found in our local CGAL web site which contains links to documentation and in particular to the CGAL getting started manual
- The paper below surveys the CGAL activities at Tel Aviv University
**Robust geometric computing in motion**[psz]

- For robustness and precision in geometric computing, see a recent comprehensive survey by Stefan Schirra which is available on-line in Schirra’s web site

**20.03.2000**Approximate swept volumes (given by Sigal Raab, 2 hours only)- Approximating swept volumes of polyhedral objects in 3-space; an algorithm by S.A. Abrams and P.K Allen, described in the paper
**Swept volumes and their use in viewpoint computation in robot work-cells**

In*Proceedings of the IEEE International Symposium on Assembly and Task Planning*, 1995, pp. 188–193

- More on precision and robustness problems

- Approximating swept volumes of polyhedral objects in 3-space; an algorithm by S.A. Abrams and P.K Allen, described in the paper
**27.03.2000**Lower envelopes, Motivation- The connection between lower envelopes and Voronoi diagrams
- Davenport-Schinzel sequences
- Algorithms for computing the lower envelope
- Most of the material is taken from the book by Sharir and Agarwal (see the course bibliography), Chapter 1. The connection between lower envelopes and Voronoi diagrams is discussed in Appendix 7.1 in the book

Assignment no. 2 [psz], due: May 1st, 2000

frame programs, example input files

**03.04.2000**Lower envelopes, cont’d, Molecular surfaces I- An improved algorithm for computing the lower envelope (Hershberger); the algorithm is described in the book by Sharir and Agarwal (see the courses bibliography), Section 6.2.2
- Introduction to 3D arrangements
- The complexity of arrangements of planes and of spheres
- The complexity of the union boundary of a collection of spheres
- “Fatness”, the favorable setting of spheres in the hard sphere model of a molecule
- Efficient intersection structure for molecules
- The material related to spheres and molecules can be found in the paper:
**Spheres, molecules, and hidden surface removal**[psz]

D. Halperin and M.H. Overmars

*Computational Geometry: Theory and Applications*11 (2), 1998, 83–102

**10.04.2000**Molecular surfaces II- The different molecular surfaces: van der Waals, Lee and Richards’s solvent accessible surface, Richard’s “smooth” molecular surface
- Computing molecular surfaces (the boundary of the union of balls/spheres)
- Alpha-hulls and molecular surfaces
- Approaches to handling degeneracies in arrangements
- Controlled perturbation of arrangement of spheres (introduction)
- The material is covered in two papers:
**Spheres, molecules, and hidden surface removal**[psz]

D. Halperin and M.H. Overmars,*Computational Geometry: Theory and Applications*11 (2), 1998, 83–102**A perturbation scheme for spherical arrangements with application to molecular modeling (MIT AI MEMO)**

D. Halperin and C.R. Shelton

The full version [psz]

Assignment no. 3 [psz], due: May 29th, 2000

frame programs, example input files

**01.05.2000**Controlled perturbation, Compact representation of the invariants of an arrangement- Controlled perturbation of arrangements of spheres
- The material is in the paper:
**A perturbation scheme for spherical arrangements with application to molecular modeling (MIT AI MEMO)**

D. Halperin and C.R. Shelton

The full version [psz]

- Compact representation of the invariants of an arrangement. Example 1: compactly storing all the maps in the aspect graph of a set of convex polygons in the plane under orthogonal projection in the plane
- Compact representation of the invariants of an arrangement

**08.05.2000**Aspect graphs in 3D- The aspect graph of a polyhedral scene under orthographic projection
- Computing the lower envelope of a set of non-intersecting triangles in 3-space: divide-and-conquer, `arrangement’ algorithm (projecting all the triangles onto the \(xy\)-plane and computing the envelope over each face)
- Compactly representing all the maps in the aspect graph. See
**Efficiently computing and representing aspect graphs of polyhedral objects**

Z. Gigus, J. Canny and R. Seidel,*IEEE Trans. Pattern Anal. Mach. Intell*. , Vol. 13. no. 6 (1991), 542–551

- (Yet another) introduction to 3D arrangements

**15.05.2000**Arrangements of triangles in 3D- The complexity of such arrangements
- Vertical decomposition of arrangement of triangles: what it is, how complex it is and how to construct it in an output-sensitive manner
- All the material covered in class appears in the paper:
**Vertical decompositions for triangles in 3-space**[pgz]

M. de Berg, L.J. Guibas and D. Halperin,*Discrete and Computational Geometry*, 15 (1996), 36–61

**22.05.2000**Arrangements of well-behaved surfaces in 3D, The area bisectors of a polygon- Arrangements of well-behaved surfaces in 3D
- The compelxity and output-sensitive computation of the vertical decomposition of such arrangements
- Navigating the arrangement through non-vertical faces
- The material covered in class appears in the later sections of the paper:
**Vertical decompositions for triangles in 3-space**[psz]

M. de Berg, L.J. Guibas and D. Halperin,*Discrete and Computational Geometry*, 15 (1996), 3–61

- The area bisectors of a polygon: introduction
- The material appears in the the paper:
**On the area bisectors of a polygon**[psz]

K.F. Böhringer, B.R. Donald and D. Halperin,*Discrete and Computational Geometry*, 22 (1999), 269–285

Assignment no. 4 [psz], due: June 12th, 2000 (in Eti Ezra’s mailbox)

frame programs, example input files

**29.05.2000**The area bisectors of a polygon- Properties of area bisectors, combinatorial bounds, output-sensitive algorithm
- The material appears in the the paper:
**On the area bisectors of a polygon**[psz]

K.F. Böhringer, B.R. Donald and D. Halperin,*Discrete and Computational Geometry*, 22 (1999), 269–285

The Final Assignment [psz], due: August 14th, 2000