4.3.98
Introduction
What is Computational Geometry? Course outline, motivation and techniques. Naive convex hull algorithms; gift wrapping (see Chapter 3 in O'Rourke's book).
11.3.98
Convex hull computation continued; Line segment intersection
Graham's O(n log n) algorithm (Chapter 1 in CGAA). 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 CGAA). 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 CGAA.
18.3.98
Doubly-connected-edge-list; Map overlay; Polygon triangulation and the
art gallery problem
The doubly connected edge list; overlay of planar subdivision (CGAA, 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.
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 CGAA, Chapter 3. (The description in class followed O'Rourke's presentation closely.)
Assignment no. 1 (ps file), due: April 1st, 1998.
25.4.98
Tetrahedralization; Intersection of halfplanes, casting
We reviewed the results for triangulation shown in the previous lesson. Next, a few facts about tetrahedralization where surveyed: not every polyhedron is tetrahedralizable with vertices of the polyhedron only (see also Assignment no. 2); the algorithm by Chazelle and Palios (see next paragraph for more details); in general putting guards at the vertices of a polyhedron is insufficient for guarding the polyhedron; there are polyhedra with $n$ vertices that require $\Omega(n^{3/2}))$ guards.
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.
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 CGAA.
The linear programming problem was presented.
1.4.98
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 CGAA. (ii) Megiddo's deterministic linear time algorithm. See Preparata and Shamos, Section 7.2.5.
Assignment no. 2 (ps file), due: April 22nd, 1998.
Video segment from CG Video Review 1993, by Jack Snoeyink, "Objects that cannot be taken apart wit two hands." Based on the paper with the same title, Snoeyink and Stolfi, Discrete and Computational Geometry, Vol. 12 (1994), pp. 367--384.
8.4.98
Orthogonal range search; Linear programming in three dimensions
Two structures for orthogonal range search were described and analyzed: kd-trees and range trees in any fixed dimension. CGAA, 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).
An extension of the randomized incremental algorithm for linear programming to three-dimensional space was presented. CGAA, Section 4.6.
22.4.98
Point location
Randomized incremental construction of trapezoidal maps, and point location search structure. CGAA, Chapter 6.
Assignment no. 3 (ps file), due: May 6th, 1998.
Programming Assignment (ps file), due: June 30th, 1998.
6.5.98
Point location cont'd; Voronoi diagrams
Tail estimate for randomized incremental construction of trapezoidal maps, and point location search structure. CGAA, Chapter 6.
Voronoi diagrams: background, definitions, combinatorial complexity. Voronoi diagrams of point sites in the plane: Fortune's algorithm. CGAA, Chapter 7.
Video segment: "Visualizing Fortune's sweepline algorithm" by Seth Teller (ACM CG Video Review 1993).
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.
Assignment no. 4 (ps file), due: May 27th, 1998.
13.5.98
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. CGAA, Chapter 8.
Computing the smallest area triangle determined by a set of points. Edelsbrunner's book, Section 12.4.
Video segment: Computing the rectangle discrepancy, by Dobkin and Gunopulos (ACM CG Video Review 1994).
27.5.98
Davenport-Schinzel sequences; Geometric problems in robotics
DS-sequences definitions, connection to envelopes, several bounds on $\lambda_s(n)$. Chpater 1 in the book "DS sequences and their geometric applications" by Sharir and Agarwal, Cambridge, 1995.
The discussion on "Area bisectors of a polygon" is taken from a paper with this title: Click here for a ps file.
Geometric problems in robotics: (1) Part orienting. (2) Maintaining structures with many degrees of freedom.
Video segments: (1) Ken Goldberg's "Feeding polygonal + polyhedral parts" USC, 1994. (2) Two pieces from ICRA '95 video review on modular robotics. (3) Endgame.
3.6.98
Delaunay triangulation; Windowing
Triangulations. Legal tringulations; edge flip. Delaunay triangulations. CGAA, Chapter 9.
Windowing. Orthogonal range search on segments in the plane. Interval trees. Priority search trees.
Assignment no. 5 (ps file), due: June 17th, 1998.
17.6.98
3D Convex hull; connections between structures; more data structures
Convex hulls in 3D. Connections between 3D convex hulls, 2D Delaunay triangulations, 2D Voronoi diagrams, lower envelopes and intersection of halfspaces. CGAA, Chapter 11.
Segment trees. CGAA, Section 10.3.
Video segments---modeling in CG: (1) Weighted 3D alpha-hulls, by Varshney et al, 3rd CG review 1994, last segment. (2) 3D modeling using the Delaunay triangulation by Geiger, 4th CG review 1995.