CS 564 Computational Geometry

Introduction: algorithmic background, data structures, geometric preliminaries, models of computation. Geometric searching:
pointlocation problems, rangesearching problems. Convex hulls: problem statement and lower bounds, convex hull algorithms
in the plane, Graham's scan, Jarvis's march, Quickhull techniques, divideandconquer algorithms, dynamic convex hull, convex hull in 3D.
Proximity: a collection of problems, a computational prototype: element uniqueness, lower bounds, the closestpair problem: a
divideandconquer approach, the Voronoi diagram, proximity problems solved by the Voronoi diagram. Triangulation: planar
triangulations, Delaunay triangulation. Intersections: application areas, planar applications: intersection of convex polygons,
intersection of starshaped polygons, intersection of line segments, 3D applications: intersection of 3D convex polyhedra,
intersection of halfspaces.
Credit units: 3 ECTS Credit units: 5.



Bilkent University Main Page
Last regenerated automatically on October 26, 2021 by OAC  Online Academic Catalog Software

