Lecture: Wednesday, 16:00–19:00, Aliyah Building, room 204
Instructor: Dan Halperin, [email protected]
Office hours: Wednesday, 19:00–20:00, Schreiber Building, room 211
Teaching Assistant: Alexander Rabinovich, [email protected]
The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in GIS (geographic information systems), computer graphics, robotics, and more.
Bibliography:
The main textbook of the course is Computational Geometry by Example by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. The book has not been published yet, but a draft copy is available from the librarians at the Exact Sciences Library. Copies of selected chapters will be distributed in class.
The full bibliographic list for the course
Assignments, Examination, and Grades:
The final grade will be determined by: 10% – homework assignments, and 90% – final exam.
Besides the regular homework assignments, one programming assignment will be given. This is TARGIL RESHUT, you can skip it if you wish. The grade for the programming assignment will be considered only if it improves your final grade, in which case the final grade’s breakdown will be: 10% – homework assignments, 20% – programming assignment, and 70% – final exam.
- Assignment no. 1 [ps], due: 13 Nov 1996
- Assignment no. 2 [ps], due: 27 Nov 1996
- Assignment no. 3 [ps], due: 11 Dec 1996
- Programming Assignment [ps]—optional, due: 1 Jan 1997
- Assignment no. 4 [ps], due: 25 Dec 1996
- Assignment no. 5 [ps], due: 8 Jan 1997
- Assignment review [ps]
Course Summary:
Below you’ll find a very brief summary of what was covered in class during the semester. This should not be taken as a complete description of the course’s contents.
- 16.10.96 Introduction
- What is Computational Geometry? Course outline, motivation and techniques. Naive convex hull algorithms (see Chapter 3 in O’Rourke’s book).
- 23.10.96 Convex hull computation continued; Line segment intersection
- Two convex hull algorithms: gift wrapping (see Chapter 3 in O’Rourke’s book) and Graham’s O(n log n) algorithm (Chapter 1 in CG by Example). The orientation test. Lower bound for convex hull algorithms.
- Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann’s plane sweep (Chapter 2 in CG by Example). A survey of more efficient algorithms for the problem.
- The last segment in CG Video Review 1992, by Tal, Chazelle, and Dobkin. Based on the paper: An optimal algorithm for intersecting line segments in the plane, by Chazelle and Edelsbrunner, J. of the ACM, Vol. 39, 1992, pp. 1–54. For recent advances on this problem see “Notes and comments” at the end of Chapter 2 of CG by Example.
- 30.10.96 Line segment intersection continued; Doubly-connected-edge-list; Map overlay
- The segment intersection predicate (O’Rourke’s book, Chapter 1). Running time analysis of the sweep algorithms for line segment intersection in the general case, allowing for degenerate input (CG by Example, Chapter 2).
- The doubly connected edge list; overlay of planar subdivision (CG by Example, Chapter 2).
- Video segment no.~1 in CG Video Review 1994, An O(n\log n) implementation of the Douglas-Peucker algorithm for line simplification, by Hershberger and Snoeyink. For details see Proc. of the 10th ACM Symposium On Computational geometry, pp. 383–384
- 6.11.96 Polygon triangulation and the art gallery problem
- We have shown that $\lfloor n/3 \rfloor$ guards are sometimes necessary and always sufficient to guard a simple polygon with n vertices. We have shown that every simple polygon can be triangulated; that the triangulation graph is 3-colorable; that the dual of the triangulation graph is a tree.A naive algorithm that mimics the triangulation existence proof can triangulate a simple polygon with n vertices in O(n^2) time. A more efficient algorithm does it in O(n\log n) by first decomposing a polygon into monotone polygons and then triangulating each of the resulting monotone subpolygons.
- The material covered in class could be found in O’Rourke’s book, Chapters 1 and 2, and in CG by Example, Chapter 3. (The description in class followed O’Rourke’s presentation closely.)
- Chazelle’s linear time algorithm for triangulating a polygon was mentioned. It is described in the paper: Triangulating a simple polygon in linear time, by B. Chazelle, Discrete and Computational Geometry, Vol. 6, pp. 485–524, 1991.
- 13.11.96 Intersection of halfplanes, casting
- We have shown an $O(n\log n)$ algorithm for computing the intersection of $n$ halfplanes. This question was motivated by a problem in casting: computing whether a given polyhedron is castable. See Chapter~4 in CG by Example.A video segment from CG Video Review 1992 by Palios and Phillips: Computing a tetrahedralization of a simple polyhedron. The segment illustrates the algorithm by Chazelle and Palios, described in their paper “Triangulating a nonconvex polytope”, Discrete and Computational Geometry, Vol. 5, pp. 505–526, 1990
- 20.11.96 Linear programming in low dimensional space
- Two algorithms were presented for linear programming in 2D: (i) A randomized incremental algorithm running in expected linear time, and demonstrated “backward analysis” for randomized algorithms. See Chapter 4 of CG by Example. (ii) A deterministic linear time algorithm. See Preparata and Shamos, Section 7.2.5.
- 27.11.96 Orthogonal range search; Linear programming in three dimensions
- An extension of the randomized incremental algorithm for linear programming to three-dimensional space was presented. See CG by Example, Section 4.6.Two structures for orthogonal range search were described and analyzed: kd-trees in any fixed dimension, and range trees in one- and two dimensions. See CG by Example, Chapter 5
- A video segment by Murphy and Skiena (ACM CG Video review 1993) describing their software “Ranger” was shown (nearest neighbor and orthogonal range search in high-dimensional space)
Assignment no. 3 [ps], due: 11 Dec 1996
Programming Assignment [ps], optional, due: 1 Jan 1997 - 4.12.96 Orthogonal range search (cntnd); Point location
- Range trees in higher dimensions. Fractional cascading. See CG by Example, Sections 5.4 and 5.6.Point location. Randomized incremental construction of trapezoidal maps. See CG by Example, Chapter 6.
- 11.12.96 Voronoi diagrams (introduction); HANUKKAH students’ presentations
- Voronoi diagrams: background, definitions, combinatorial complexity.
- 18.12.96 Voronoi diagrams (cntnd)
- Voronoi diagrams of point sites in the plane: Fortune’s algorithm. See CG by Example, Chapter 7. Survey of extensions.Video segments: (1) “Visualizing Fortune’s sweepline algorithm” by Seth Teller (ACM CG Video Review 1993); (2) “Interactive visualization of weighted 3D alpha hulls” by Varshney, Brooks and Wright (ACM CG Video review 1994).Additional references: (1) F. Aurenhammer, Voronoi diagrams: A survey of a fundamental geometric data structure , ACM Comput. Surv. 23 (1991), pp. 345–405. (2) A book full of applications—A. Okabe, B. Boots and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams , John Wiley & Sons, 1992.
- 25.12.96 Arrangements of lines; Duality
- Point-line duality. Incremental construction of arrangements of lines. Computing the halfplane discrepancy of a set of points in a square. CG by Example, Chapter 7.Computing the smallest area triangle determined by a set of points. Edelsbrunner’s book, Section 12.4.Video segment: Topologically sweeping an arrangement (ACM CG Video Review 1992). Assignment no. 5 [ps], due: 8 Jan 1997
- 01.01.97 Delaunay triangulation
- A brief survey of extensions of arrangements (higher dimensions, segments, surfaces).
- Triangulations. A randomized incremental algorithm for computing the Delaunay triangulation. CG by example, Chapter 9. (To be continued.)Video segment: 3D Modeling using the Delaunay triangulation, by Bernhard Geiger (ACM CG Video Review 1995). Assignment review [ps]
- 08.01.97 Delaunay triangulation (cntnd); Interval trees, windowing, priority search trees
- Analysis of the randomized incremental construction of the Delaunay triangulation.Orthogonal range search on segments in the plane. Interval trees. Priority search trees.Video segments: (1) Maintenance of the set of segments visible from a moving viewpoint in 2D, by Ghali and Stewart (ACM CG Video Review 1996); (2) Computing the rectangle discrepancy, by Dobkin and Gunopulos (ACM CG Video Review 1994).
- 15.01.97 — the last lesson Convex hull in 3D; Segment trees
- The complexity of the convex hull of a set of points in 3D. A survey of algorithms for computing the hull: (1) gift wrapping, (2) deterministic algorithm, Preparata and Hong (see the book by Preparata and Shamos in the bibliography list), and (3) incremental construction: for details of the deterministic version see O’Rourke’s book, for the randomized version see CG by Example, Chapter 11.The connections between convex hulls, intersection of halfspaces, and Voronoi diagrams. CG by Example, Chapter 11.A linear time algorithm for computing the convex hull of a simple polygon, Graham and Yao 1983.Segment trees. Windowing of arbitrarily oriented disjoint segments. CG by Example, Chapter 10.