CSC 674: Computational Geometry

Offered Under: M.Sc. in Computer Science (CSC)

Searching and Geometric Data Structures : Balanced binary search trees, Priority-search trees, Range searching, Interval trees, Segment trees, Algorithms and complexity of fundamental geometric objects: Polygon triangulation and Art gallery theorem, Polygon partitioning, Convex-hulls 2- and 3- dimension, Dynamic convex-hulls,; Geometric intersection: Line segment intersection and the plane-sweep algorithm, Intersection of polygons; proximity: Voronoi diagrams, Delunay triangulations, closest and furthest pair: Visualization: Hidden surface removal and binary space partition (BSP) trees; Graph Drawings: Drawings of rooted trees (Layering, Radial drawings, HV-Drawings, Recursive winding), Drawings of planar graphs (Straight-line drawings, Orthogonal drawing, Visibility drawings); Survey of recent developments in computational geometry.

  • None

Course Type Major
Credit Hour 3
Lecture Hour 45
Expected Outcome(s):

Suggested Books:

Grading Policy: