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