COMP 163: Computational Geometry



Prerequisites (further details are given in each web chapter below)

Each of the following web chapters for this course contains class notes, in the form of 163-chapterXX.pdf, as well as other online notes, applets, papers and projects from various sources.

Contents (not all will be covered)
  1. Basic concepts
  2. Polygons (finding diagonals and ears; triangulating)
  3. Art gallery problems and more triangulation. Polygonal decomposition into convex pieces.
  4. Monotone polygons: triangulation, testing monotonicity, decomposing polygons into monotone pieces.
  5. Convex hull of a point set
  6. Convex hull of simple polygon
  7. Visibility regions, kernels and star-shaped polygons
  8. Rotating calipers, curves of constant width.
  9. Point location
  10. Voronoi diagrams and Delaunay triangulations
  11. Proximity graphs
  12. Range counting
  13. Interval overlap, rectangle overlap, 2D line segment intersections
  14. Duality
  15. Linear programming in 2D
  16. Ham-sandwich cuts. The Borsuk-Ulam theorem.
  17. Combinatorial geometry
  18. Data depth
  19. Geometry and computing in ancient times: straight edge and compass
  20. Model of computation



  Intro


  1. Some basics (General position, types of polygons, Jordan curve theorem, determining if a point is in a polygon. Area of polygons)
    • No prerequisites.
    1. 163-chapter01.pdf
    2. General position, and types of polygons
    3. Jordan curve theorem (it suffices to know what this is; details not required)
      1. wiki on Jordan curve theorem
      2. pdf notes on Jordan's theorem for polygons by Jeff Erickson.
      3. pdf note on Jordan curve theorem from page by Andrew Ranicki. (extract from What is Mathematics? (OUP, 1941, 2nd ed. 1996) by R. Courant and H. Robbins).
      4. More about Jordan and the Koch snowflake
      5. Alexander horned sphere
    4. Determining if two line segments intersect
      • notes by Rodrigo Silveira
    5. Determining if a point is inside a polygon
    6. Computing the area of a polygon
    7. Tangents between points and polygons


  2. Finding diagonals in polygons, finding "ears", and triangulating.
    • Prerequisite knowledge: induction, geometric series. Chapter 1.4
    1. 163-chapter02.pdf
    2. project on triangulations, ears, diagonals, etc, by Ian Garton.
    3. Paper on Finding an ear in linear time (just browse if you're interested)
    4. Notoriously difficult paper by Bernard Chazelle, for linear-time triangulation of polygons.
    5. Finding diagonals that balance polygonal partition. See 163-chapter02B.pdf


  3. Art gallery problems and more triangulation. Polygonal decomposition into convex pieces.
    • Prerequisite knowledge: recursion, Euler's formula, pigeonhole principle.
    1. 163-chapter03.pdf
    2. A few pages from the course notes by David Mount, on the Euler formula and art gallery problem.
    3. An applet on 3-coloring a polygonal triangulation by Thierry Dagnino.
    4. Further exploration of convex decomposition and visibility:
      Applet that finds smallest number of convex pieces (not covered in class). Here's another applet that does the same. This could be a project for you: describe the optimal algorithm, or if it is much too complicated, some of the key aspects, and hopefully design a more descriptive applet. Google finds lots of results on approximate convex decomposition, so you could look into that too. I am not familiar with such approximations.


  4. Monotone polygons: triangulation, testing monotonicity, decomposing polygons into monotone pieces.
    • Prerequisite knowledge: induction, balanced binary search trees.
    1. 163-chapter04.pdf
    2. Linear-time decomposition of a polygon into monotone pieces, and subsequent triangulation, are covered in these notes by David Mount.
    3. A short paper on testing monotonicity in linear time is here. Click on the left of the second item (Preparata & Supowit).


  5. Convex hull of a point set
    • Prerequisite knowledge: amortization. For 7.6, obviously divide and conquer. For 7.7, geometric series and non-beginner big-O.
    1. Brute force and incremental.
    2. Jarvis march
      1. wiki
      2. demo
    3. Graham scan
      1. A simple description from MIT.
      2. demo
      3. Notes by David Mount. (see pages 13-15)
    4. Quick-hull
      1. wiki
      2. demo
    5. Divide and Conquer (merge-hull)
      1. Notes by David Mount.
    6. Advanced algorithms
      1. Kirkpatrick-Seidel "ultimate" convex hull algorithm
        1. Notes by Samir Khuller. This uses prune and search, which takes advantage of the geometric series... as in: xkcd 994 & xkcd 1153
      2. Chan's algorithm.
        1. Here is his paper. Focus on sections 1-2 and on page 5.
    7. Lower bounds (besides the simple comparison-model lifting argument)
      1. Paper by Jeff Erickson (including brief survey)
      2. Paper by Michael Ben-Or
      3. Paper by David Avis (full text available). Reference [6] should be added here too, if found.
      4. Paper by Andrew Yao.
    8. Project by Cyrus Cousins (former comp-163 student).


  6. Convex hull of simple polygon: Sklansky scan, WEV polygons, Melkman's algorithm.
    • Prerequisite knowledge: stacks, queues (mainly for Melkman).
    1. 163-chapter06.pdf
    2. Page on linear-time algorithms for computing the convex hull of a simple polygon. See the section on Melkman, and use the applet provided (if it works anymore).
    3. Excellent modern tutorial on Melkman's algorithm, by Max Goldstein (former comp-163 student).
    4. Melkman's paper


  7. Visibility regions, kernels and star-shaped polygons
    • Prerequisite knowledge: amortization, induction. (partially: 2-ear theorem, Melkman's algorithm)
    1. 163-chapter07.pdf
    2. Two applets showing the kernel and visibility polygon from a point. You can drag all input and see how things change.
    3. Visibility: Section 8.2 (p.203) in the book by O'Rourke, entitled Art Gallery Theorems and Algorithms, describes how to compute the visibility region of a point in a polygon. There are many project opportunities in this book.
    4. Computing the kernel of a polygon
      1. in O(nlogn) time by Shamos and Hoey. (the paper does other things too).
      2. in linear time by Lee and Preparata.
    5. Triangulating star-shaped polygons
      1. with knowledge of the kernel.
        • (uses the two-ear theorem)
        1. Interactive visualization by Max Goldstein (former comp-163 student).
      2. without knowledge of the kernel
        • (uses Melkman's algorithm in one step)
        1. Here is a paper containing information on how to triangulate a star-shaped polygon without knowing the kernel (and much more). Page 3, and 6-7 are relevant. Note that in the paper the first step is to use the visibility polygon from an edge instead of an arbitrary boundary point, but that is because we do something more general later on. The principle for a star-shaped polygon is the same.
          This whole paper would make a great project.
        2. Interactive visualization by Ben Weitzman (former comp-163 student).
      3. Drawing a star... xkcd 1029


  8. Rotating calipers, curves of constant width.
    • Prerequisite knowledge: just the basics
    1. 163-chapter08.pdf
    2. Rotating calipers
      1. Project by Hormoz Pirzadeh on rotating calipers. The applet did not work for me recently. Please let me know if it works for you. Otherwise this might be a potential project.
      2. Another nice rotating calipers applet by Nir Efrat.
      3. A project on how not to compute the diameter of a convex polygon, by Matthew Suderman.
    3. Curves of constant width, like the Reuleaux triangle
      1. cut-the-knot.org
      2. A page on applications of such curves, by Chris Sangwin
      3. Page on the Reuleaux triangle by Paul Kunkel.
      4. wiki about the Wankel engine.


  9. Point location
    1. Prerequisite knowledge: triangulation, geometric series.
    2. 163-chapter09.pdf
    3. Slab method
    4. Kirpatrick's data structure
      1. notes by David Mount.
      2. Interactive demo by Eliot Alter (former comp-163 student).
      3. Project by Paul Sandulescu.


  10. Voronoi diagrams and Delaunay triangulations
    • Prerequisite knowledge: triangulations, graphs, amortization.
      • 163-chapter10a.pdf (Voronoi diagrams; properties and applications. The Voronoi game)
      • 163-chapter10b.pdf (basic computation of Voronoi diagram. Delaunay triangulations and their properties)
      • 163-chapter10c.pdf (overview of advanced computation. The medial axis. Voronoi in non-Euclidean metrics)
    1. Notes by David Mount.
    2. wiki - just browse through
    3. extensive notes by Franz Aurenhammer and Rolf Klein.
    4. Notes by Vera Sacristan about paraboloid/plane intersections, and their projections (only first page).
    5. Notes by Robert Pless about the Delaunay - paraboloid - 3D convex hull connection.
    6. Applets
      1. by Rashid Bin Muhammad (permits dragging points when creating them. Ignore the notes)
      2. Voroglide (can delete points, and drag points after you first let go when inserting) (demo included; see menu at top)
      3. applets for many Voronoi diagrams (different metrics, etc. Use "click" versions)
      4. Farthest point Voronoi and smallest enclosing circle applet
      5. Taxi cab geometry (L1 metric)
    7. Voronoi game
      1. voronoigame.com (see also the explanation)
      2. Multi-player (with several computer opponent modes)
      3. A paper on the Voronoi game in 2D.
    8. Applications and art
    9. Fortune's sweep algorithm: The wiki has a nice animation. You can see the output develop step-by-step here.
    10. Textbook chapters
      • O'Rourke's book: chapter 5: p.155-165, and p.170-173, and p.179-188.
      • de Berg et al.: Chapters 7.1 and 9.1, 9.2, 9.3.


  11. Proximity graphs
    • Prerequisite knowledge: understanding the concept of a graph
    1. 163-chapter11.pdf
    2. This paper is about the relative neighborhood graph. It contains a proof that the RNG is a superset of the MST (end of p.6).
    3. Some proximity graph relations are described in this project (see the "properties" section), which also has an applet allowing you to compare the graphs.
    4. The Spheres-of-Influence graph is discussed here and here, with applets.
    5. alpha-shapes are related to this topic (and to convex hulls).
    6. And just one last proximity graph.


  12. Range counting
    • Prerequisite knowledge: augmented binary search trees. See my comp160 page.
    1. kd trees
    2. range trees
    3. Notes by David Mount.


  • Interval overlap, rectangle overlap, 2D line segment intersections
    • Prerequisite knowledge: augmented binary search trees
    1. 163-chapter13.pdf
    2. Notes by David Mount.


  • Duality
    • Prerequisite knowledge: how to express a line as an equation.
    1. 163-chapter14.pdf
    2. Explore two different versions of duality: link 1 ... link 2


  • Linear programming in 2D
    • Prerequisite knowledge: how to express a line as an equation. Geometric series.
    1. A paper by Nimrod Megiddo containing the algorithm for LP in 2D (section 2). It also contains extensions and applications.
    2. Another paper by Megiddo on LP for any fixed dimension.
    3. In this link see section 4 for the 2D LP algorithm. See this applet but ignore the description.
    4. Project by Zhe Lu (former comp-163 student).


  • Ham-sandwich cuts. Brief description of the Borsuk-Ulam theorem and related concepts
    • Prerequisite knowledge: Duality (only for ham-sandwich)
    1. 163-chapter16.pdf
    2. Here is a link about the time complexity of finding a ham sandwich cut.
    3. Borsuk-Ulam
      1. A youtube presentation.
      2. wiki
    4. Brouwer fixed-point theorem
      1. wiki. The "illustrations" section lists three fascinating properties.
    5. Hairy ball theorem.
      1. wiki
      2. One proof of the hairy ball theorem is in this paper .
      3. Here is another informal "proof".
    6. Project by Greg Bodwin (former comp-163 student)


  • Combinatorial geometry
    • Prerequisite knowledge: permutations and combinations. Induction.
    1. Theorems by Helly, Radon, Tverberg, and Caratheodory.
      1. 163-chapter17a.pdf
      2. Helly wiki
      3. Radon wiki
      4. Tverberg wiki
      5. Caratheodory wiki
      6. Notes by Igor Pak on Helly's theorem (p.11), Radon's theorem (p.12), Caratheodory's theorem (p.20) and the colorful Caratheodory theorem (p.21), and a weaker version of Tverberg's theorem (p.22).
    2. Horton sets
      1. 163-chapter17b.pdf
      2. Horton's paper on -no- empty heptagons (requires permission).
    3. Empty k-gons in point sets, and the Erdos-Szekeres theorem.
      1. 163-chapter17c.pdf
      2. Here's the wiki for the Erdos-Szekeres theorem on finding monotone paths in point sets. Look at the pigeonhole principle section. This proof is easier than the lemma in the original paper, which is not only about this problem.
      3. Wiki for finding k-gons in point sets.
      4. In the book Lectures on Discrete Geometry by Jiri Matousek, you will find material on empty pentagons and heptagons, and Horton sets. See chapter 3.2, p.34. Chapter 3 starts with a proof of the Erdos-Szekeres theorem that any k-gon can be found, given a sufficiently large set of size f(k).
      5. Example of research on finding many empty pentagons.


  • Data depth
    • Prerequisite knowledge: for some topics it helps to understand geometric series and duality.
    1. Introduction
      1. 163-chapter18a.pdf
      2. Intro to some data depth functions.
      3. The Fermat-Weber problem: minimizing the sum of distances to points in a data set: wiki.
    2. Computation
      1. 163-chapter18b.pdf
      2. Computing halfspace and simplicial depths, and lower bounds: paper.
      3. Oja depth lower bound: paper.
      4. Computing the simplicial and Oja medians: see this paper.
      5. See this paper for how to compute the halfspace median in O(nlog3n) time.
      6. More info on data depth.
    3. Equipartition of lines
      1. 163-chapter18c.pdf
      2. See Lemma 7 in this paper. It defines an equipartition of lines an shows how it can be computed in O(n) time.
    4. Centerpoints
      1. 163-chapter18d.pdf
      2. In the lecture notes by Igor Pak, Theorem 2.2 (p.20) establishes how many simplices must contain some point. It is proved on p.22. Note that it uses a slightly weaker version of the Tverberg theorem.
      3. In the book Lectures on Discrete Geometry by Jiri Matousek, you will find material on using Helly's theorem to find a centerpoint for halfspace depth. See chapter 1.4 (page 14), theorem 1.4.2.


  • Geometry and computing in ancient times: straight edge and compass (independent topic)
    • Prerequisite knowledge: circles, parallelograms....
    1. 163-chapter19.pdf
    2. Great demo on the straight edge and compass by Francois Labelle. Here is a mirror site. Please let me know if the demo doesn't load.
    3. Another great tool to discover straight edge and compass constructions.
    4. wiki
    5. Further reading
      1. wiki for compass equivalence theorem
      2. wiki for Mohr-Mascheroni theorem
      3. wiki for Poncelet-Steiner theorem


  • Model of computation (for reference)
    1. pdf on algebraic decision trees by Jeff Erickson.
    2. Details on the connection between the RAM and algebraic decision tree models can be found in:
      W. Paul and J. Simon. Decision trees and random access machines. Logic and Algorithmics, Monograph 30, L'Enseignement Mathematique, 1980.