Computational Geometry
Spring, 2007
Robert Hochberg

Topics to be covered:
1. Art Gallery theorems
2. 2d Convex hulls
3. 3d Convex hulls
4. Voronoi diagrams and Delaunay triangulations
5. Arrangements
6. Randomized algorithms and backward analysis
7. Planar point location and the Kirkpatrick hierarchy



Assignments:


Links:
Great
animation of Fortune's Algorithm for computing Voronoi Diagrams.
Some screen shots of Fortune's
Algorithm
in action
Website of our
textbook's author
The Open Problem
Project at Smith College
My other web page
A note on image
maps
A great geometry
site



UnitDistance Graphs:
A UnitDistance Graph
is a graph which can be drawn in the plane so that every edge has
length
exactly 1. (Vertices are points in the plane...)
Three unitdistance graphs are shown here.
It has been an open problem for about 50 years to decide if all
unitdistance graphs can be 4colored. That is, is it possible to
assign a color to each vertex so that vertices with an edge between
them
are given different colors. It is known that 7 colors suffice,
but it is not known for 4, 5 or 6 colors.


Arrangements of Lines:
Given n lines in the plane
which do not all pass through a single common point, prove that there
must be some line with at least (n
 1)/2 points of intersection. Please! Nobody can do this!
The arrangement shown at the top of this page is an extreme
example: 11 lines, and no more than 5 points of intersection on
any line. Since line arrangements are duals of point
arrangements,
it is equivalent to consider the point version of this open
problem: Given n points
in the plane which do not all lie on a single line, show that there
must be some point which has at least (n
 1)/2 induced lines passing through it (induced by passing through
other points in the set).



Study
guide for Exam 1
This section lists the material that you are expected to
know for this first exam.
1 Polygon Triangulation {1} 1.1 Art Gallery Theorems {1} 1.1.1 Polygons {1} Definition of a Polygon {1} 1.1.2 The Art Gallery Theorem {3} Problem Definition {3} Visibility {3} Max over Min Formulation {4} Empirical Exploration {5} Sufficiency of n. {5} Necessity for Small n. {5} Necessity of n/3 {7} 1.1.3 Fisk's Proof of Sufficiency {7} Diagonals and Triangulation {8} Three Coloring {8} 1.2 Triangulation: Theory {13} 1.2.1 Existence of a Diagonal {14} 1.2.2 Properties of Triangulations {16} 1.2.4 3coloring Proof {17} 1.3 Area of Polygon {19} 1.3.1 Area of a Triangle {19} 1.3.3 Determinant Form {20} 1.3.4 Area of a Convex Polygon {20} 1.3.5 Area of a Convex Quadrilateral {21} 1.3.6 Area of a Nonconvex Quadrilateral {22} 1.3.7 Area from an Arbitrary Center {23} 1.5 Segment Intersection {32} 1.5.1 Diagonals {32} 1.6.1 Diagonals, internal or external {37} 1.6.5 Triangulation by Ear Removal {41} 1.6.7 Analysis {48} 3 Convex Hulls in Two Dimensions {73} 3.1 Definitions of Convexity and Convex Hulls {74} 3.1.1 Extreme points {76} 3.2 Naive Algorithms for Extreme Points {77} 3.2.1 Nonextreme points {77} 3.2.2 Extreme Edges {78} 3.2.3 Exercises {78} 3.3 Gift Wrapping {79} 3.4 QuickHull {81} 3.4.1 Exercises {83} 3.5 Graham's Algorithm {84} 3.5.1 Top Level Description {84} 3.5.2 Pseudocode, Version A {85} 3.5.3 Details: Boundary Conditions {85} Start and Stop of Loop {86} Sorting Origin {86} Collinearities {87} Hull Collinearities. {87} Sorting Collinearities. {88} Avoiding Floats. {92} 3.7 Incremental Algorithm {103} 3.8 Divide and Conquer {105} 3.8.1 DivideandConquer Recurrence Relation {106} 3.8.2 Algorithm Description {106} 3.8.3 Analysis {107} 4 Convex Hulls in Three Dimensions {119} 4.1 Polyhedra {119} 4.1.1 Introduction {119} 4.1.2 Regular Polytopes {123} 4.1.3 Euler's Formula {125} 4.1.4 Proof of Euler's Formula {125} 4.2.2 Divide and Conquer {129} Discarding hidden faces {132} 4.2.3 Incremental Algorithm {134} Complexity Analysis {136} 5 Voronoi Diagrams {181} 5.1 Applications: Preview {181} 5.2 Definitions and Basic Properties {183} Two Sites {184} Three Sites {184} 5.2.1 Halfplanes {185} Four Sites {185} Many Sites {186} 5.2.2 Size of Diagram {186} 5.3 Delaunay Triangulations {188} 5.3.1 Properties of Delaunay Triangulations {188} 5.3.2 Properties of Voronoi Diagrams {191} 5.3.3 Exercises {192} 5.4 Algorithms {193} 5.4.1 Intersection of Halfplanes {193} 5.5 Applications in Detail {198} 5.5.1 Nearest Neighbors {198} Nearest Neighbor Queries {198} All Nearest Neighbors {199} 5.5.2 Triangulation maximizing the minimum angle {199} 5.5.3 Largest Empty Circle {200} Centers inside the Hull {201} Centers on the Hull {202} Algorithm {203} 5.5.4 Minimum Spanning Tree {203} Kruskal's algorithm {204} MST is a subset of the DT {204} 5.7.2 Twodimensional Delaunay triangulations {215} 3D Hull to Delaunay Triangulation: O(n^2) Code {221} 6 Arrangements {227} 6.1 Introduction {227} 6.2 Combinatorics of Arrangements {229} 6.2.1 Zone Theorem {230} 6.2.2 Exercises {233} 6.3 Incremental Algorithm {234}
6.5 Duality {236}
6.5.1 Duality mapping {237}
6.5.2 Duality Properties {237}
Some Combinatorial Geometry
Sylvester's Theorem
(that in any finite set of points, not all on a line, there
is some line through exactly two points)
Two proofs of Sylveste's Theorem
By least pointline distance
By duality, and the fact that planar graphs must have a vertex of degree <= 5
That any set of n points, not all on a line, must determine at least n slopes
proof by allowable sequences of permutations
That in any configuration of n red and n blue points, there is some
crossingfree matching of red points to blue points
Proof by minimal total length of matching
7 Search and Intersection 257
7.4 Point in Polygon {279}
7.4.2 Ray crossings {280}
7.7 Intersection of Segments {308}
7.10 Extremal Polytope Queries {317}
7.10.1 Sketch of Idea {318}
7.10.2 Independent Sets {318}
7.10.3 Independent Sets: Properties and Algorithm {322}
7.10.4 Construction of Nested Polytope Hierarchy {324}
Space Requirements {324}
Retriangulating Holes {325}
Linking Polytopes {325}
7.10.5 Extreme Point Algorithm {325}
Extreme Edges {327}
7.11 Planar Point Location {332}
7.11.1 Applications {332}
7.11.2 Independent Set Algorithm {333}
8 Motion Planning {343}
8.1 Introduction {343}
8.1.1 Problem Specification {343}
8.1.2 Outline {344}
8.2 Shortest Paths {344}
8.2.1 Visibility Graphs {344}
8.2.2 Constructing the Visibility Graph {346}
8.2.3 Dijkstra's algorithm {347}
Spreading Paint {347}
Algorithm {347}
Time Complexity {349}
8.2.4 Exercises {349}
8.3 Moving a Disk {350}
8.3.1 Minkowski Sum {350}
8.3.2 Conceptual Algorithm {352}
8.4 Translating a Convex Polygon {352}
8.4.1 Minkowski Sum Example {352}
8.4.2 Minkowski Addition {353}
8.4.3 Constructing the Minkowski Sum {354}
8.4.4 Implementation of Minkowski Convolution {356}
8.4.5 Conceptual Motion Planning Algorithm {362}
8.4.6 Exercises {364}
8.5 Moving a Ladder {365}
8.5.1 Cell decomposition {368}
Definition of a Cell {368}
Connectivity Graph G_\theta {368}
Critical Orientations {370}
Connectivity graph G {371}
Randomized Algorithms
Not on final exam
