CS 531: Computational Geometry - Department of Computer Science - Purdue University Skip to main content

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.


Last Updated: Apr 25, 2017 4:53 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone: (765) 494-6010 • Fax: (765) 494-0739

Copyright © 2023 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.