Bilkent University Logo

Bilkent University

Online Academic Catalog

Undergraduate and Graduate Programs 2024-2025


CS 478 Computational Geometry

Introduction: algorithmic background, data structures, geometric preliminaries, models of computation. Geometric searching: point-location problems, range-searching problems. Convex hulls: problem statement and lower bounds, convex hull algorithms in the plane, Graham's scan, Jarvis's march, Quickhull techniques, divide-and-conquer algorithms, dynamic convex hull, convex hull in 3D. Proximity: a collection of problems, a computational prototype: element uniqueness, lower bounds, the closest-pair problem: a divide-and-conquer 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 star-shaped polygons, intersection of line segments, 3D applications: intersection of 3D convex polyhedra, intersection of half-spaces. Credit units: 3 ECTS Credit units: 5, Prerequisite: CS 202.

Bilkent University Main Page

Last regenerated automatically on December 10, 2024 by OAC - Online Academic Catalog Software