mca Syllabus

Computational Geometry
Code : CS 704E
Credits: 3
Module I [12]

Introduction

• historical perspective
• algorithmic background
• geometric preliminaries
• initial forays

Convex hulls

• problem statement and lower bounds
• convex hull algorithms
• convex hulls in >2 dimensions
• extensions and applications

Module II [18]

Polygon approximation

• triangular approximations
• k-gonal approximations
• restricted approximations
• other criteria of approximation

Geometric searching

• point-location problems
• range-searching problems

Module III [15]

Proximity

• Typical problems and lower bounds
• Closest pair problem
• Voronoi diagrams
• Minimum spanning trees
• Triangulations

Miscellaneous problems

• (More) Art gallery problems
• Intersections
• Pattern recognition
• Parallel computational geometry

Books:
1. Laszlo, Computational Geometry, PHI
2. M.de Berg, Computational Geometry-algorithms & applications,Springer India
Modeling & Simulation