3 Credit Hour Course
Intended For Level 0 Term 0 Students
Prerequisite:
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 in 2-dimension 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 drawings, Visibility drawings); Survey of recent developments in computational geometry.
