EdusalsaDiscover Your Stanford

CS 268

Geometric Algorithms

  • autumn

3 units

Letter or Credit/No Credit

Techniques for design and analysis of efficient geometric algorithms for objects in 2-, 3-, and higher dimensions. Topics: convexity, triangulations and simplicial complexes, sweeping, partitioning, and point location. Voronoi/Delaunay diagrams and their properties. Arrangements of curves and surfaces. Intersection and visibility problems. Geometric searching and optimization. Random sampling methods. Range searching. Impact of numerical issues in geometric computation. Example applications to robotic motion planning, visibility preprocessing and rendering in graphics, and model-based recognition in computer vision. Prerequisite: discrete algorithms at the level of 161. Recommended: 164.

Course Prequisites



Sign Up

To save CS 268 to your course bucketlist

Already Have An Account? Log In