Topic Outline

Preliminaries

• Introduction, overview, geometric primitives, models of computation

Geometric optimization

• exposure to a variety of techniques encountered in the course as they apply to one basic problem (convex hull construction). These include divide-and-conquer, sweeping algorithms (dimensionality reduction), incremental algorithms, dynamic algorithms, randomization, geometric transformations and duality, worst-case and expected-case analysis, output-size sensitivity, and lower bounds.
• low dimensional linear programming and applications
• convex hulls in higher dimensions

Representation of geometric structures

• introduction to fundamental geometric data structures for the representation of planar subdivisions, polyhedra and line arrangements
• dealing with degeneracies

Geometric search

• planar point location
• overview of data structures (such as range trees, segment trees and interval trees) that arise in the study of orthogonal range searching

Proximity problems

• closest site
• Voronoi diagrams
• nearest neighbours and clustering
• facility location
• sensor networks

Spatial decompositions

• triangulations (of point sets and polygons)
• trapezoidal decomposition
• mesh generation
• binary space partitions

Combinatorial geometry

• combinatorics of line arrangements, envelopes, duality
• halving lines
• ham sandwich cuts

Geometric intersection detection and construction

• segment intersection
• intersection of half spaces
• polygon and polyhedral intersection

Visibility and motion planning

• visibility graphs; Art Gallery theorems
• shortest paths; terrains and obstacles
• constrained motion planning
• kinetic algorithms

Approximation techniques

• well-separated sets
• spanners
• epsilon nets
• solving problems with imprecise/uncertain data

Planar graph drawing

• Schnyder woods, canonical orderings
• orthogonal drawings
• universal point sets

Contact & intersection representation of graphs

• segments, disks, T-shapes, triangles, boxes

Proximity graphs

• Gabriel, Delaunay, Beta, rectangle of influence
• Euclidean minimum spanning tree

Visibility graphs

• bar visibility, bar-k visibility, outerplanar

Geographic graphs

• map labelling, cartograms, flow

Force-directed graph drawing

• springs, magnetic fields, repulsion