Computational Geometry is a branch of computer science devoted to the systematic study of algorithms and data structures for geometric objects. The problems in this arena are often motivated by major application domains, e.g., robotics, geographic information systems, integrated circuit design, computer-aided engineering, computer vision, machine learning, etc.
Course Contents:
Introduction: What is computational geometry?
Convex hulls of point sets in the plane.
Computing/detecting intersections among a set of line segments.
Polygons, triangulation, visibility.
Linear programming in low dimensions.
Orthogonal Range searching: Find the points in a query box.
Point location search: Find a query point in a subdivision.
Voronoi diagrams and Delaunay triangulations.
Arrangements of lines, hyperplanes.
Geometric duality, polarity
Visibility graphs, shortest paths, motion planning.
Binary space partitions.
Randomized algorithms for geometric problems.
Geometric optimization, approximation algorithms.
Clustering, data summarization, machine learning.
Learning Objectives:
This is an introductory course on computational geometry and its applications. We will discuss techniques needed in designing and analyzing efficient algorithms and data structures for computational problems in discrete and combinatorial geometry. After successful completion of this course, students will be able to -
explain fundamental concepts, structures, and problem definitions in computational geometry.
explain, analyze and evaluate the discussed algorithms.
select and adapt appropriate algorithms and data structures to related problems.
model and analyze unknown applied or theoretical geometric problems and develop and possibly implement efficient solutions independently.
Selected Readings:
"Computational Geometry: Algorithms and Applications" by de Berg, Cheong, van Kreveld, and Overmars (3rd Edition). [Online version - 2nd edition].
"Computational Geometry: An Introduction" by Preparata and Shamos. [Online version].
"Computational Geometry in C", 2nd Edition by O’Rourke (2nd Edition). [Online version].
"Discrete and Computational Geometry" by Devadoss and O’Rourke.
"Algorithms in Combinatorial Geometry" by Herbert Edelsbrunner.
"Geometric Approximation Algorithms" by Sariel Har-Peled. [Online version].
"Handbook of Discrete and Computational Geometry" by Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth. [Online version - 3rd edition].