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 Unit-Distance Graphs: A Unit-Distance 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 unit-distance graphs are shown here. It has been an open problem for about 50 years to decide if all unit-distance graphs can be 4-colored.  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 3-coloring 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 Divide-and-Conquer 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 Two-dimensional 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 point-line 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 crossing-free 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