Topic

No. of hours

Lecture

Tutorial/Practical

Computational Geometry Introduction :-

An Example :- Convex Hulls.

Degeneracies and Robustness.

Application Domains.

3

3

-

Line Segment Intersection Thematic Map Overlay :-

Line Segment Intersection.

The Doubly-Connected Edge List.

Computing the Overlay of Two Subdivisions.

Boolean Operations.

3

3

-

Polygon Triangulation Guarding an Art Gallery :-

Guarding and Triangulations.

Partitioning a Polygon into Monotone Pieces.

Triangulating a Monotone Polygon.

3

3

-

Linear Programming Manufacturing with Molds :-

The Geometry of Casting.

Half-Plane Intersection.

Incremental Linear Programming.

Randomized Linear Programming.

Unbounded Linear Programs.

Linear Programming in Higher Dimensions.

Smallest Enclosing Discs.

3

3

-

Orthogonal Range Searching Querying a Database :-

1-Dimensional Range Searching.

Kd-Trees.

Range Trees.

Higher-Dimensional Range Trees.

General Sets of Points.

Fractional Cascading.

3

3

-

Point Location Knowing Where You Are.

Point Location and Trapezoidal Maps.

A Randomized Incremental Algorithm.

Dealing with Degenerate Cases.

A Tail Estimate.

3

3

-

Voronoi Diagrams The Post Office Problem :-

Definition and Basic Properties.

Computing the Voronoi Diagram.

Voronoi Diagrams of Line Segments.

Farthest-Point Voronoi Diagrams.

3

3

-

Arrangements and Duality :-

Super sampling in Ray Tracing.

Computing the Discrepancy.

Duality.

Arrangements of Lines.

Levels and Discrepancy.

3

3

-

Delaunay Triangulations Height Interpolation :-

Triangulations of Planar Point Sets.

The Delaunay Triangulation.

Computing the Delaunay Triangulation.

The Analysis.

A Framework for Randomized Algorithms.

3

3

-

More Geometric Data Structures Windowing :-

Interval Trees.

Priority Search Trees.

Segment Trees.

3

3

-

Convex Hulls Mixing Things :-

The Complexity of Convex Hulls in 3-Space.

Computing Convex Hulls in 3-Space.

The Analysis.

Convex Hulls and Half-Space Intersection.

Voronoi Diagrams Revisited.

3

3

-

Binary Space Partitions The Painter's Algorithm :-

The Definition of BSP Trees.

BSP Trees and the Painter's Algorithm.

Constructing a BSP Tree.

The Size of BSP Trees in 3-Space.

BSP Trees for Low-Density Scenes.

3

3

-