Computational Geometry

Course Name: 

Computational Geometry (CS421)


B.Tech (CSE)




Programme Specific Electives (PSE)

Credits (L-T-P): 



Introduction: Historical perspective, Geometric preliminaries. Convex hulls algorithms in 2D and 3D, lower bounds.
Triangulations: Polygon triangulations, Representations, Point-set triangulations. Voronoi diagrams: Algorithms,
Closest pair problems. Delaunay triangulations: algorithms (divide-and-conquer, flip, incremental), Duality of
voronoi diagrams, Properties (min-max angle). Geometric searching: Point-location, 2D linear programming with
prune and search. Visibility: Algorithms for weak and strong visibility, Visibility with reflections, Art-gallery
problems. Arrangements of lines: 2D arrangements, zone theorem, Many-faces complexity, algorithms. Sweep
techniques: Plane sweep for segment intersections, Fortune's sweep for Voronoi diagrams, Topological sweep for line
arrangements. Combinatorial geometry: Ham-sandwich cuts, Helly's theorems, k-sets. Rectilinear geometry:
Intersection and union of rectangles, Rectangle searching. Robust geometric computing. Applications of
computational geometry.


Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer.
F. P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer. Joseph O' Rourke,
Computational Geometry in C, Cambridge University Press. Lecture Notes by David Mount.

Contact us

Dr. Manu Basavaraju
Head of the Department
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Hot line: +91-0824-2474053
Email: hodcse[AT]nitk[DOT]ac[DOT]in


Connect with us

We're on Social Networks. Follow us & get in touch.