EECS 6114:
Computational Geometry
Tentative SYLLABUS
- Introduction
and geometric
preliminaries. .............................................................
[1.5 hours]
- Convex
Hulls in 2D - Algorithms
and Applications
....................................................
[3 hours]
- Line
Segments Intersection - Thematic
Map Overlay
................................................. [3 hours]
- Triangulation
of Polygons - Guarding
an Art Gallery
...............................................
[2 hours]
- Linear
Programming - Manufacturing
with Molds
.....................................................
[6 hours]
- Orthogonal
Range Searching - Querying
a DataBase .................................................
[2 hours]
- kD Trees
- Range Trees
- Fractional Cascading
- Point Location in a Planar
Subdivision - Knowing Where You
Are on the Map ...... [2.5 hours]
- Arrangements and Geometric
Duality - Super Sampling in Ray
Tracing
.................. [3.5
hours]
- Ham-Sandwich Cuts - Answering Half-Plane Range
Queries
- Topological Sweep - Collinearity
& Smallest Area Triangle
- Voronoi
Diagram and Delaunay Triangualtion
....................................................... [8.5
hours]
- Divide-&-Conquer
- Plane Sweep
- Randomized
Incremental Construction
- via d+1
dimensional Convex Hull
- edge-flip
- Proximity
space partitioning and the post office problem
- Height
Interpolation
- Euclidean:
Minimum Spanning Tree, Traveling Salesman Problem,
- Minimum Weight Triangulation, Relative
Neighborhood and Gabriel Graphs.
- Higher Order
VD
- Generalized
metrics - Robot Motion
Planning
- Windowing
(More Geometric Data Structures)
......................................................... [1
hour]
- Interval
Trees
- Priority
Search Trees
- Segment Trees
- Convex Hull in
3 and higher Dimensions ...................................................................
[2 hours]
- Binary Space
Partitions - The Painter's
Algorithm
........................................................
[2 hours]
- Quad Trees - Non-uniform
Mesh Generation ..................................................................
[2 hours]
- o
o o