Computational Geometry

Points, lines, circles and ellipses as primitives, scan conversion algorithms for primitives, Fill area primitives including scan-line polygon filling, inside-outside test, boundary and flood-fill, character generation, line attributes, area-fill attributes, character attributers. The Digital Differential Analyzer (DDA), Bresenham’s Algorithm, Generation of Circles. Geometric Preliminaries - General definitions and notations, General definitions and notations, Geometry duality. Polarity

Introduction to Geometric Searching, Point-Location Problems, General considerations. Simple cases, Location of a point in a planar subdivision, The slab method, The chain method, Optimal techniques: the planar-separator method, the triangulation refinement method, and the bridged chain method, The trapezoid method, Range-Searching Problems. 1D Range search, Kd Trees.

Delaunay Triangulations - Triangulations and planar point sets, The Delaunay Triangulation, Computing the Delaunay Triangulation. Geometric Data Structures - Interval Trees, Priority Search Trees, Segment Trees

Art Gallery Theorem, Guarding Art Gallery, Fisk’s proof using three colouring. Arrangements of Lines – Duality, Combinatorics of arrangements, Zone Theorem, Algorithm for Constructing arrangements of lines.

Convex Hulls- Convex Hull Algorithms in the Plane -Graham’s Scan Algorithm, Jarvi’s March, Divide and Conquer Algorithm. Voronoi Diagrams- Properties and applications in the plane. Proofs of properties related to vertices and edges of voronoi diagrams. Algorithm for constructing voronoi diagram. Delaunay Triangulation.