- Future Students
- Academic Progams
- Undergraduate Program
- Current Semester CS Courses
- New Course Offerings
- Upcoming Semesters
- Previous Semesters
- Canonical Syllabi
- Course Access & Request Policy
- Academic Integrity Policy
- Grad Student Registration
- Variable Title Courses
- Study Abroad
- Professional Practice
- Co-Op Professional Practice
- Non-Co-Op Professional Practice
- ISS Application Process for International Students (CPT, OPT, RCL, Program Extension, COEL)
- Pass/Not Pass Spring 2020
CS 531: Computational Geometry
List of Topics (By Week):
Convex hull of points. Efficiency considerations. Implementation strategy. Role of floating-point arithmetic.
Segment intersection, sweep line paradigm. Primary data vs. computed quantities. Robustness.
Intersection of subdivisions of the plane. Relationship to solid modeling.
Polygon triangulation, y-monotone decomposition, application to rendering. Practical considerations.
Linear programming and geometric applications.
Range search in one and two dimensions. kd-trees, range trees, interval trees.
Range search continued; fractional cascading.
Voronoi diagram construction; applications.
Voronoi structures for higher geometric primitives; medial axis. Applications in CAD.
Delaunay triangulation and key properties. Applications in finite element meshing.
Arrangements and duality; applications to anti-aliasing. Other transformations with applications.
BSP trees; applications in virtual reality. Conversion from boundary representation to constructive solid geometry.
Segment and window queries; box intersection. Applications in collision detection and solid modeling.
Convex hull in 3-space.
Voronoi diagram interpretation in 3D.