COMP 163: Computational Geometry
Prerequisites (further details are given in each web chapter below)
 knowledge of bigO notation is assumed for almost all lectures. Fairly basic, unless noted otherwise.
 recursion, divide and conquer; proof by induction/contradiction.
 basic data structures such as linked lists, arrays, stacks, and balanced binary search trees are mentioned occasionally.
Typically it suffices if the student understands what can be achieved by such structures.
 amortization (nothing fancy)
 basic properties and algorithms for graphs, occasionally
Each of the following web chapters for this course contains class notes, in the form of 163chapterXX.pdf, as well as other online notes, applets, papers and projects from various sources.
Contents (not all will be covered)
 Basic concepts
 Polygons (finding diagonals and ears; triangulating)
 Art gallery problems and more triangulation. Polygonal decomposition into convex pieces.
 Monotone polygons: triangulation, testing monotonicity, decomposing polygons into monotone pieces.
 Convex hull of a point set
 Convex hull of simple polygon
 Visibility regions, kernels and starshaped polygons
 Rotating calipers, curves of constant width.
 Point location
 Voronoi diagrams and Delaunay triangulations
 Proximity graphs
 Range counting
 Interval overlap, rectangle overlap, 2D line segment intersections
 Duality
 Linear programming in 2D
 Hamsandwich cuts. The BorsukUlam theorem.
 Combinatorial geometry
 Data depth
 Geometry and computing in ancient times: straight edge and compass
 Model of computation
Intro
 Some basics (General position, types of polygons, Jordan curve theorem, determining if a point is in a polygon.
Area of polygons)
 163chapter01.pdf
 General position, and types of polygons
 Jordan curve theorem (it suffices to know what this is; details not required)
 wiki on Jordan curve theorem

pdf notes on Jordan's theorem for polygons by Jeff Erickson.
 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).
 More about Jordan and the Koch snowflake
 Alexander horned sphere
 Determining if two line segments intersect
 notes by Rodrigo Silveira
 Determining if a point is inside a polygon
 Computing the area of a polygon
 Tangents between points and polygons
 Finding diagonals in polygons, finding "ears", and triangulating.
 Prerequisite knowledge: induction, geometric series. Chapter 1.4
 163chapter02.pdf
 project on triangulations, ears, diagonals, etc, by Ian Garton.
 Paper on Finding an ear in linear time
(just browse if you're interested)
 Notoriously difficult paper by Bernard
Chazelle, for lineartime triangulation of polygons.
 Finding diagonals that balance polygonal partition. See
163chapter02B.pdf
 Art gallery problems and more triangulation. Polygonal decomposition into convex pieces.
 Prerequisite knowledge: recursion, Euler's formula, pigeonhole principle.
 163chapter03.pdf
 A few pages from the course notes by David Mount, on the Euler formula and art gallery problem.
 An applet on 3coloring a polygonal triangulation by Thierry Dagnino.
 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.
 Monotone polygons: triangulation, testing monotonicity, decomposing polygons into monotone pieces.
 Prerequisite knowledge: induction, balanced binary search trees.
 163chapter04.pdf
 Lineartime decomposition of a polygon into monotone pieces, and subsequent triangulation, are covered in these
notes by David Mount.
 A short paper on testing monotonicity in linear time is
here. Click on the left of the second item (Preparata & Supowit).
 Convex hull of a point set
 Prerequisite knowledge: amortization. For 7.6, obviously divide and conquer. For 7.7, geometric series and nonbeginner bigO.

 Brute force and incremental.
 Jarvis march
 wiki
 demo
 Graham scan
 A simple description from MIT.
 demo
 Notes by David Mount. (see pages 1315)
 Quickhull
 wiki
 demo
 Divide and Conquer (mergehull)
 Notes by David Mount.
 Advanced algorithms
 KirkpatrickSeidel "ultimate" convex hull algorithm
 Notes by Samir Khuller.
This uses prune and search, which takes advantage of the geometric series...
as in: xkcd 994 &
xkcd 1153
 Chan's algorithm.
 Here is his paper.
Focus on sections 12 and on page 5.
 Lower bounds (besides the simple comparisonmodel lifting argument)
 Paper by Jeff Erickson (including brief survey)

Paper by Michael BenOr

Paper by David Avis (full text available).
Reference [6] should be added here too, if found.
 Paper by Andrew Yao.
 Project by Cyrus Cousins (former comp163 student).
 Convex hull of simple polygon: Sklansky scan, WEV polygons, Melkman's algorithm.
 Prerequisite knowledge: stacks, queues (mainly for Melkman).
 163chapter06.pdf
 Page on lineartime algorithms for computing the
convex hull of a simple polygon. See the section on Melkman, and use the applet provided (if it works anymore).
 Excellent modern
tutorial on Melkman's algorithm, by Max Goldstein (former comp163 student).
 Melkman's paper
 Visibility regions, kernels and starshaped polygons
 Prerequisite knowledge: amortization, induction. (partially: 2ear theorem, Melkman's algorithm)
 163chapter07.pdf
 Two applets showing the kernel and visibility polygon from a point.
You can drag all input and see how things change.
 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.
 Computing the kernel of a polygon
 in
O(nlogn) time
by Shamos and Hoey. (the paper does other things too).
 in linear time by Lee and Preparata.
 Triangulating starshaped polygons
 with knowledge of the kernel.
 (uses the twoear theorem)
 Interactive visualization by
Max Goldstein (former comp163 student).
 without knowledge of the kernel
 (uses Melkman's algorithm in one step)
 Here is a paper
containing information on how to triangulate a starshaped polygon without knowing the kernel (and much more). Page 3, and 67 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 starshaped polygon is the same.
This whole paper would make a great project.
 Interactive visualization by Ben Weitzman (former comp163 student).
 Drawing a star... xkcd 1029
 Rotating calipers, curves of constant width.
 Prerequisite knowledge: just the basics
 163chapter08.pdf
 Rotating calipers
 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.
 Another nice rotating calipers
applet
by Nir Efrat.
 A project on how not to compute the diameter of a convex polygon, by Matthew Suderman.
 Curves of constant width, like the Reuleaux triangle
 cuttheknot.org
 A page
on applications of such curves, by Chris Sangwin
 Page on the Reuleaux triangle by Paul Kunkel.
 wiki about the Wankel engine.
 Point location
 Prerequisite knowledge: triangulation, geometric series.
 163chapter09.pdf
 Slab method
 Kirpatrick's data structure
 notes
by David Mount.
 Interactive demo by Eliot Alter (former comp163 student).
 Project by Paul Sandulescu.
 Voronoi diagrams and Delaunay triangulations
 Prerequisite knowledge: triangulations, graphs, amortization.

 163chapter10a.pdf
(Voronoi diagrams; properties and applications. The Voronoi game)
 163chapter10b.pdf
(basic computation of Voronoi diagram. Delaunay triangulations and their properties)
 163chapter10c.pdf
(overview of advanced computation. The medial axis. Voronoi in nonEuclidean metrics)
 Notes by David Mount.
 wiki  just browse through
 extensive notes by
Franz Aurenhammer and Rolf Klein.
 Notes by Vera Sacristan about
paraboloid/plane intersections, and their projections (only first page).
 Notes by Robert Pless about the
Delaunay  paraboloid  3D convex hull connection.
 Applets
 by Rashid Bin Muhammad (permits dragging points when creating them. Ignore the notes)
 Voroglide
(can delete points, and drag points after you first let go when inserting) (demo included; see menu at top)
 applets for many Voronoi diagrams
(different metrics, etc. Use "click" versions)
 Farthest point Voronoi and smallest enclosing circle applet
 Taxi cab geometry (L1 metric)
 Voronoi game
 voronoigame.com (see also the explanation)
 Multiplayer (with several computer opponent modes)
 A paper on the Voronoi game in 2D.
 Applications and art
 Fortune's sweep algorithm:
The wiki has a
nice animation. You can see the output develop stepbystep
here.
 Textbook chapters
 O'Rourke's book: chapter 5: p.155165, and p.170173, and p.179188.
 de Berg et al.: Chapters 7.1 and 9.1, 9.2, 9.3.
 Proximity graphs
 Prerequisite knowledge: understanding the concept of a graph
 163chapter11.pdf
 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).
 Some proximity graph relations are described in this
project
(see the "properties" section), which also has an applet allowing you to compare the graphs.
 The SpheresofInfluence graph is discussed
here and
here, with applets.

alphashapes are related to this topic (and to convex hulls).
 And just one last proximity graph.
 Range counting
 Prerequisite knowledge: augmented binary search trees
 163chapter12.pdf
 Notes by David Mount.
 kd tree wiki
 Range tree wiki
 Interval overlap, rectangle overlap, 2D line segment intersections
 Prerequisite knowledge: augmented binary search trees
 163chapter13.pdf
 Notes by David Mount.
 Duality
 Prerequisite knowledge: how to express a line as an equation.
 163chapter14.pdf
 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.

 A paper by Nimrod Megiddo containing the algorithm for LP in 2D (section 2). It also contains extensions and applications.
 Another paper by Megiddo on LP for any fixed dimension.
 In this
link see section 4 for the 2D LP algorithm. See this
applet
but ignore the description.
 Project by Zhe Lu (former comp163 student).
 Hamsandwich cuts. Brief description of the BorsukUlam theorem and related concepts
 Prerequisite knowledge: Duality (only for hamsandwich)
 163chapter16.pdf
 Here is a
link
about the time complexity of finding a ham sandwich cut.
 BorsukUlam
 A youtube presentation.
 wiki
 Brouwer fixedpoint theorem
 wiki.
The "illustrations" section lists three fascinating properties.
 Hairy ball theorem.
 wiki
 One proof of the hairy ball theorem is in this paper .
 Here is another
informal "proof".
 Project by Greg Bodwin (former comp163 student)
 Combinatorial geometry
 Prerequisite knowledge: permutations and combinations. Induction.
 Theorems by Helly, Radon, Tverberg, and Caratheodory.
 163chapter17a.pdf
 Helly wiki
 Radon wiki
 Tverberg wiki
 Caratheodory wiki
 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).
 Horton sets
 163chapter17b.pdf
 Horton's paper on no empty heptagons (requires permission).
 Empty kgons in point sets, and the ErdosSzekeres theorem.
 163chapter17c.pdf
 Here's the wiki for the ErdosSzekeres 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.
 Wiki for finding kgons in point sets.
 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 ErdosSzekeres theorem that any kgon can be found, given a sufficiently large set of size f(k).
 Example of research on finding many empty pentagons.
 Data depth
 Prerequisite knowledge: for some topics it helps to understand geometric series and duality.
 Introduction
 163chapter18a.pdf
 Intro to some data depth functions.
 The FermatWeber problem: minimizing the sum of distances to points in a data set:
wiki.
 Computation
 163chapter18b.pdf
 Computing halfspace and simplicial depths, and lower bounds:
paper.
 Oja depth lower bound: paper.
 Computing the simplicial and Oja medians: see this paper.
 See this paper for
how to compute the halfspace median in O(nlog^{3}n) time.
 More info on data depth.
 Equipartition of lines
 163chapter18c.pdf
 See Lemma 7 in this paper.
It defines an equipartition of lines an shows how it can be computed in O(n) time.
 Centerpoints
 163chapter18d.pdf
 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.
 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....
 163chapter19.pdf
 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.
 Another great tool to discover straight edge and compass constructions.

wiki
 Further reading

wiki for compass equivalence theorem

wiki for MohrMascheroni theorem

wiki for PonceletSteiner theorem
 Model of computation (for reference)
 pdf on algebraic decision trees by Jeff Erickson.
 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.