Schedule

What is Computational geometry? Connections with theoretical computer science, graphics, structural bioinformatics (molecular docking on the right). Computational model: real RAM.

Convex hull in 2d (CH2). Lower bound via Sorting. Gift-wrapping algorithm (Jarvis, see right-hand side figure). Orientation Predicate, or CCW (counter-clockwise) for 3 points. Incremental algorithm (Βeneath-beyond) and upper bound. Extreme points.

Theory Assignment 1. Solution.

Demos from older programming assignments: Wrap2D, Marriage-before-Conquest, 3d CH. Demos 2010: Μ.Ζερβός, Δανελάκης-Σαϊτη.

Extension to CH3 (fullerene C_60 molecule on the right). General dimension, polytopes, facets, faces. Types of polytopes: simplex/simple/simplicial polytopes, normal cones.

Theory Assignment 2. Solution.

Lower/upper hull, projection, regular/nonregular triangulations, Secondary graph/polytopes, Gelfand-Kapranov-Zelevinsky theorem. Flips (including degenerate cases). See Book "Triangulations" by DeLoera, Rambau, Santos (pp.5-36,41-57-72).

Theory Assignment 3. Solution.

Intro to Python (slides). Connection with CGAL. Graphical input/output with library "visual" of Python.

1st programming assignment. Technical notes. Solutions. Grades.

Non convex polygons and their triangulations. Visibility. Guarding a polygon: Art Gallery Problem and Theorem. Placing ⌊n/3⌋ guards via a triangulation. NP-hardness of minimizing the number of guards. (Maximization problems given a fixed number of guards, approximation.)

Linear programming, Simplex algorithm, complexity.
Theory Assignment 4. Solution.

Gift-wrapping and time/space complexity analysis in 3 and general dimensions. Output-sensitive complexity. Reverse search on the facets: spanning tree by Simplex paradigm, total ordering of facets, DFS traversal.
Theory Assignment 5. Solution.

Equivalence of Upper hull construction with the Intersection of Lower halfplanes. Duality between points and lines in 2D, points and planes in 3D.
2nd Programming Assignment. Technical notes. Selected Solutions. Grades.

Orientation predicate, degeneracy, symbolic perturbation (figure on the right).

Minkowski sum of polygons, properties and computation: Algorithm (rotating calipers), non-convex polygons (using triangulation). Decomposition: NP-completeness (reduction to Subset-Sum, connection to k-SUM); poly-time for constant-size summands (video.avi).

Regular polyhedral subdivisions of point sets and mixed regular subdivisions of Minkowski sums of convex polygons. Cayley trick: the connection between them. (slides)

Applications:
(1) Study of polynomial equations: Newton polytopes, Mixed volume.
(2) Robot motion: Minkowski Sums of nonconvex polygons and polytopes (figure on the right).
Theory Assignment 6. Solution.

Delaunay triangulation in 2d. Lower bound via CH2. Algorithms, edge flip. InCircle predicate. Construction by projecting 3d convex hull.

Voronoi diagram, extension to any dimension. Construction by projecting halfspace intersection. demo.

Geometric search in 2 and higher dimensions: kd-trees, Range trees. Fractional cascading (slides from other course).
Theory Assignment 7. Solution.

Course projects. Projects discussion program