Introduction to Computational Geometry

Instructor: Don Sheehy
Email: donald@engr.uconn.edu
Class Meets: MW 3-4:15 in Oak Hall 109 (map)
Office Hours: MW 9-10am
Office: ITEB 361

See the Course Policies.

The material covered this semester will differ some from the similar course last fall, but there will be some overlap. Here is a link to the course website for last year's course. Computational Geometry - Fall 2013

Lecture Notes

  1. What is Computational Geometry (8/25/2014 Notes)

    In this first lecture, I gave a high level overview of the types of problems we will see in the class. Then, we explored some ideas from the computational geometers of antiquity, focusing on Ruler and Compass constructions a la Euclid.

  2. Linear Predicates (8/27/2014 Notes)
    (Listen to this lecture on audio)

    Today, we saw how to generalize the comparison model to geometric problems. We saw that computing the sign of the determinant is usually for answering simple linear questions.

  3. More on Determinants and Linear Predicates (9/3/2014 Notes)
    (Listen to this lecture on audio)

    Today, we looked in more detail at determinants, their computation, and linear predicates. We saw that computing the sign of the determinant can also solve a quadratic question like testing if a point inside a circle via the parabolic lifting.

  4. Convex Hulls in the Plane (9/8/2014 Notes)
    (Listen to this lecture on audio)

    This lecture introduced the convex hull problem for points in the plane. We gave a simplistic algorithm and observed its relationship to Selection Sort. Then, we build a comparator from a line side test and used it in the Graham Scan algorithm.

  5. Simple Polygons and the Jordan Curve Theorem (9/10/2014 Notes)
    (Listen to this lecture on audio)

    This lecture covered some more connections between polygons and determinants, gave some results about simple (possibly nonconvex) polygons. We also proved the Polygonal Jordan Curve Theorem.

    See HuskyCT, for scans of two proofs of the Jordan Curve Theorem from textbooks.

  6. Planar Straight-Line Graphs (9/15/2014 Notes)
    (Listen to this lecture on audio)

    We covered the basics of planar straight-line graphs.

  7. Data Structures for Planar Straight-Line Graphs (9/17/2014 Notes)
    (Listen to this lecture on audio)

    We saw the half-edge data structure for representing a planar straight-line graph.

  8. Posets, Duality, and Barycentric Coordinates (9/22/2014 Notes)
    (Listen to this lecture on audio)

    Today we saw how the incidence structure of a PSLG induces a POSET structure. We represented that POSET both as a Hasse diagram and in the barycentric decomposition.

  9. Polyhedral Complexes and Triangulations of Point Sets (9/24/2014 Notes)
    (Listen to this lecture on audio)

    We looked closer at polyhedral complexes as a more general type of geometric structure that we can represent via its poset (or barycentric decomposition).

  10. Delaunay Triangulations of Point Sets (9/29/2014 Notes)
    (Listen to this lecture on audio)

    We introduced the Delaunay triangulation and demonstrated its local characterization.

  11. Incremental Delaunay Triangulation (10/01/2014 Notes)
    (Listen to this lecture on audio)

    We gave an incremental algorithm for computing Delaunay triangulation. We also showed that the Delaunay triangulation minimizes the maximum angle among all triangulations of a point set.

  12. Randomized Incremental Delaunay Triangulation (10/08/2014 Notes)
    (Listen to this lecture on audio)

    We analyzed the point location cost for Delaunay triangulation.

  13. Voronoi Diagrams (10/13/2014 Notes)

    We introduced Voronoi diagrams and saw that they are duals (as polyhedral complexes) to Delaunay triangulations.

  14. Introduction to Projective Duality (10/15/2014 Notes)
    (Listen to this lecture on audio)

    We introduced projective duality by reflection across a parabola (or paraboloid).

  15. Exercises in Projective Duality (10/20/2014 Notes)

    We worked through several examples of projective duality and its usefulness in representing sets of lines as sets of points (and vice versa).

  16. Halfspace Range Counting (10/22/2014 Notes)
    (Listen to this lecture on audio)

    We used line arrangements to solve the halhspace range counting problem. We also proved the Zone Theorem.

  17. Point Location in a Planar Subdivision (10/27/2014 Notes)

    We generalized the point location that we saw for incremental delaunay triangulation in order to do point location in an arbitrary planar subdivision.

  18. Tutte's Algorithm I (11/03/2014 Notes)
    (Listen to this lecture on audio)

    We introduced Tutte's classic "spring embedding" of a graph.

  19. Tutte's Algorithm II (11/05/2014 Notes)
    (Listen to this lecture on audio)

    We proved Tutte's algorithm is correct.

  20. The Maxwell-Ceremona Correspondence (11/10/2014 Notes) (More Notes) (Even More Notes)
    (Listen to this lecture on audio)

    The Maxwell Cremona correspondence connects equilibrium stresses and liftings.

  21. Steinitz's Theorem (11/12/2014 Notes)

    Every simple, planar, 3-connected graph is the edge skeleton of a convex 3-dimensional polytope.

  22. Weighted Delaunay Triangulations (11/17/2014 Notes)
    (Listen to this lecture on audio)

    This lecture gave a more general picture of the lift-convex hull-project approach that we used for the Delaunay traingulation. The result is weighted Delaunay triangulations, which have a natural dual, weighted Voronoi diagrams. I then noted how Koebe embeddings are a special case and gave a construciton of the secondary polytope of triangulations of a point set.

  23. Koebe Embeddings (11/05/2014 Notes)
    (Listen to this lecture on audio)

    We covered polyhedral courvature, the discrete Gauss-Bonnet theorem, and used theseto give an algorithm for Koebe embeddings.

  24. From Low Dimensions to High Dimensions (12/1/2014 Notes)

    We reviewed the main topics of the course with a special attention to the ways that linear algebra allowed us to "see" in high dimensions.