Computational Geometry (COMP 5008)
Office: Herzberg Building 5125C
Lectures: Monday, 2:35-5:25pm, Canal Building 2400
Office hours: Tuesday, 10:15-noon
Computational Geometry is concerned with the design of efficient
techniques for the computer-based representation and manipulation
of geometric objects. The field has been in existence for about
fourty years and has blossomed into a mature body of efficient
algorithmic techniques. This has not only led to a solid theoretical
understanding of the complexity of geometric problems, but also to
the development of several efficient and widely-used software
libraries for a wide variety of basic geometric problems.
These techniques have the potential to bring about significant design
and performance improvements in applied fields such as
Computer-Aided Design and Manufacturing, Cartography,
Geographic Information Systems, and Materials Science.
Prerequisites: Basic knowledge in algorithms and data structures
(as covered in the courses COMP 3804 and 4804).
- Convex hull algorithms
- Triangulations of point sets
- Euler's formula for planar graphs, with applications
- The k-set problem
- Point location in planar subdivisions
- Multi-level data structures (range trees, segment trees,
interval trees, priority search trees)
- Plane sweep algorithms
- Voronoi diagrams and Delaunay triangulations
- Lower envelopes and Davenport-Schinzel sequences
- Computing the diameter of a point set
- Algorithms for geometric optimization problems
- Triangulations of polygons
- The course will mainly be based on lecture notes which will be posted
on this page.
- Some chapters from the following book will be covered:
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.
Algorithms and Applications,
3rd edition, Springer-Verlag, 2008.
This book is available
through the Carleton library.
- 3 Assignments (50%).
- Project (40%). The project can either be (i) an implementation
(with documentation) of a geometric algorithm, or (ii) a survey
paper about a specific topic in computational geometry.
- Project Presentation (10%). Each student will make a 15-minute
presentation about their project; the schedule will be fixed in
- Assignment 1 is due October 16, in class.
- Assignment 2 is due November 6, in class.
- Assignment 3 is due December 4, in class.
What was done in class:
- September 11: Computing the
convex hull of a planar point set.
- September 18:
- More on convex hulls, intersection of halfplanes, point-line
duality, from the notes above.
- Introduction to
linear programming, Chapter 4 in the textbook.
- September 25:
- October 2:
- October 9: Thanksgiving
- October 16:
- October 30:
- November 6:
- November 13:
- November 20:
- November 27:
- December 4:
- Friday December 8: Student presentations, 15 minutes per student.
You can connect your laptop to the computer in the classroom.
You can also bring a USB stick and upload your file to the
computer in the classroom.
- Important dates:
- End of reading week: Your project proposal must have
been submitted to me.
- December 15: Deadline for project submission.
- You are welcome to come up with any interesting topic that has a
strong geometric content.
- Write software that visualizes (and explains) an algorithm that we
have seen in class.
- Implement one of the algorithms that we have seen in class and do
experiments on large inputs.
- Take one of the topics that we have seen in class or is in the
textbook, and write a survey about other results that are known for
- The Delaunay triangulation shows up in many application areas
(including non-computer-science areas).
Write a survey on how and why the Delaunay triangulation is used.
- Write a survey on algorithms for the point location problem in
- Write a survey on nearest-neighbor searching.
- Write software that visualizes (and explains) the duality transform
between points and lines, and the relationship between the
intersection of halfplanes and convex hulls.
- Write a survey on Art Gallery Theorems.
- Write a survey on facility location problems.
- Implement several convex hull algorithms (such as Gift Wrapping and
Graham's Scan) and compare the running time in different scenarios.
- Implement Kirkpatrick's data structure for point location and do
experiments on large planar graphs.
- Write a survey on hidden-surface removal algorithms.
- Implement and experiment with range trees.
- Implement Voronoi diagram and Delaunay triangulation.
- Implement and visualize k-d trees and quad trees.