Copyright 2019 - CSIM - Asian Institute of Technology

Computational Geometry and Applications

Course code: AT70.16
Credits: 3(3–0)
This course is elective

Course objectives

To provide students with an introduction to both the theory and applications of the discipline of computational geometry which is concerned with the solving of computational problems arising from geometric questions. Essential theory and algorithms will be covered and content will be motivated by practical problems. Implementations of geometric algorithms in a high-level language will be covered. Course will be seminar-style.

Learning outcome

Geometric Algorithms and Analysis. Geometric Data Structures. Convex Hull Theory and Computation. Segment Intersection. Polygon Triangulation. Geometric Linear Programming. Voronoi Diagrams. Delaunay Triangulation. Point Location. Motion Planning. Binary Space Partition. Special Topics.


Data Structures and Algorithms, or Instructor Consent.

Course outline

I.          Convex Hulls
1.     Properties
2.     Algorithms
3.     Handling Degeneracy and Robustness
4.     Applications Domains
II.        Line Segment Intersections
1.     Algorithms
2.     Plane Sweep Method
3.     Doubly-Connected Edge List
4.     Application Domains
III.       Polygon Triangulation
1.     Properties
2.     Algorithms
3.     Applications Domains
IV.       <

Learning resources


M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: 
Computational Geometry: Algorithms and Applications (2nd Edition), Springer Verlag, 2000.


J-D. Boissonnat and M. Yvinec:
Algorithmic Geometry, Cambridge University Press, 1998.
K. Mulmuley:
Computational Geoemetry: An Introduction through Randomized Algorithms, Prentice Hall, 1998.
J. O’Rourke:
Computational Geometry in C (2nd Edition), Cambridge University Press, 1998.
F. P. Preparata and M. I. Shamos:
Computational Geometry: An Introduction, Springer-Verlag, 1991.

Reference books

International Journal of Computational Geometry and Applications, World Scientific.
Computational Geometry: Theory and Applications, Elsevier.

Back to the list


Login Form


School of Engineering and technologies     Asian Institute of Technology