CS 531: Computational Geometry

List of Topics (By Week):

1. Convex hull of points. Efficiency considerations. Implementation strategy. Role of floating-point arithmetic.

2. Segment intersection, sweep line paradigm. Primary data vs. computed quantities. Robustness.

3. Intersection of subdivisions of the plane. Relationship to solid modeling.

4. Polygon triangulation, y-monotone decomposition, application to rendering. Practical considerations.

5. Linear programming and geometric applications.

6. Range search in one and two dimensions. kd-trees, range trees, interval trees.

7. Range search continued; fractional cascading.

8. Voronoi diagram construction; applications.

9. Voronoi structures for higher geometric primitives; medial axis. Applications in CAD.

10. Delaunay triangulation and key properties. Applications in finite element meshing.

11. Arrangements and duality; applications to anti-aliasing. Other transformations with applications.

12. BSP trees; applications in virtual reality. Conversion from boundary representation to constructive solid geometry.

13. Segment and window queries; box intersection. Applications in collision detection and solid modeling.

14. Convex hull in 3-space.

15. Voronoi diagram interpretation in 3D.

2000.09