Computational Geometry (COMP 5008)
Winter Semester 2017
Office: Herzberg Building 5125C
Lectures: Friday, 11:35-2:25pm, Canal Building 2400
Office hours: Tuesday, 10-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 February 10, in class.
- Assignment 2 is due March 3, in class.
- Here is Assignment 2 as a
- Here is the LaTeX file.
- Assignment 3 is due March 17, in class.
- Here is Assignment 3 as a
- Here is the LaTeX file.
What was done in class:
- January 6: Computing the
convex hull of a planar point set.
- January 13: More on convex hulls, intersection of halfplanes,
point-line duality, from the notes above.
- January 20:
- January 27:
- February 3:
- February 10:
- February 17:
- February 24: no class because of reading week.
- March 3:
- March 10: Darryl Hill talked about routing algorithms.
- March 17:
- Lower envelopes and Davenport-Schinzel sequences.
- The Ackermann function.
More on the Ackermann function; this function is slightly
different from the one we saw in class.
- March 24:
- The greedy spanner; part of this is from
- Spanners: the Theta-graph and skip list spanners; from
- March 31:
- Sink spanners, how to combine them with the Yao-graph
to obtain a spanner of bounded degree (Arya, Das, Mount,
Salowe, Smid. Euclidean spanners: short, thin, and lanky.
Proceedings 27th ACM Symposium on the Theory of Computing
(STOC), 1995, pp. 489-498.)
The Art Gallery Theorem: Chapter 3 in the textbook.
- April 7: 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.
- Friday April 21: 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.