Preface {v} 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.1.4 Exercises {11} 1.2 Triangulation: Theory {13} 1.2.1 Existence of a Diagonal {14} 1.2.2 Properties of Triangulations {16} 1.2.3 Triangulation Dual {16} 1.2.4 3-coloring Proof {17} 1.2.5 Exercises {18} 1.3 Area of Polygon {19} 1.3.1 Area of a Triangle {19} 1.3.2 Cross Product {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.3.8 Volume in Three and Higher Dimensions {25} 1.3.9 Exercises {26} 1.4 Implementation Issues {27} 1.4.1 Representation of a Point {27} Arrays versus Records {27} Integers versus Reals {28} Point Type Definition {28} 1.4.2 Representation of a Polygon {28} 1.4.3 Code for Area {29} 1.5 Segment Intersection {32} 1.5.1 Diagonals {32} 1.5.2 Problems with Slopes {32} {1.5.3} |Left| {33} 1.5.4 Boolean Inte 34 Improper Inte {36 Betweenness {36} 1.5.5 Segment Inte Code {37} 1.6 Triangulation: Implementation {37} 1.6.1 Diagonals, internal or external {37} 1.6.2 InCone {38} 1.6.3 Diagonal {40} 1.6.4 Exercises {41} 1.6.5 Triangulation by Ear Removal {41} Diagonal-Based Algorithm {42} Ear Removal {42} Triangulation Code {43} 1.6.6 Example {44} 1.6.7 Analysis {48} 1.6.8 Exercises {49} 2 Polygon Partitioning {51} 2.1 Monotone Partitioning {51} 2.1.1 Monotone Polygons {52} Properties of Monotone Polygons {52} 2.1.2 Triangulating a Monotone Polygon {54} 2.2 Trapezoidalization {54} 2.2.1 Plane sweep {56} 2.2.2 Triangulation in O(n log n) {58} 2.2.3 Exercises {59} 2.3 Partition into Monotone Mountains {59} 2.3.1 Monotone Mountains {59} 2.3.2 Triangulating a Monotone Mountain {60} 2.3.3 Adding Diagonals to Trapezoidalization {61} 2.3.4 Exercises {63} 2.4 Linear-Time Triangulation {65} 2.4.1 Randomized Triangulation {66} 2.5 Convex Partitioning {67} 2.5.1 Optimum Partition {67} 2.5.2 Hertel and Mehlhorn Algorithm {69} 2.5.3 Optimal Convex Partitions {70} 2.5.4 Exercises {70} 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} Coincident Points. {88} 3.5.4 Pseudocode, Version B {89} 3.5.5 Implementation of Graham's Algorithm {89} Data Representation {89} Sorting {90} |FindLowest|. {90} Avoiding Floats. {92} |Atan2|. {92} Slopes. {93} |Left|. {93} |Qsort|. {93} |Compare|. {94} |Main| {94} Code for the Graham Scan {96} Example {96} 3.5.6 Conclusion {100} 3.5.7 Exercises {100} 3.6 Lower Bound {101} 3.7 Incremental Algorithm {103} 3.7.1 Exercises {105} 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} 3.8.4 Output-size Sensitive Optimal Algorithm {110} 3.8.5 Exercises {111} 3.9 Additional Exercises {111} 3.9.1 Polygon Hull {111} 3.9.2 Orthogonal polygons {111} 3.9.3 Miscellaneous Hull-Related {113} 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.1.5 Consequence: Linearity {127} 4.1.6 Exercises {127} 4.2 Hull Algorithms {129} 4.2.1 Gift Wrapping {129} 4.2.2 Divide and Conquer {129} Discarding hidden faces {132} Exercises {134} 4.2.3 Incremental Algorithm {134} Complexity Analysis {136} 4.3 Implementation of Incremental Algorithm {137} 4.3.1 Data Structures {137} Structure definitions. {137} Example of Data Structures. {139} Head pointers. {141} Basic List Processing. {142} |structs|: Full Detail. {142} 4.3.2 Example: Cube {145} |main|. {145} |ReadVertices|. {145} |DoubleTriangle|. {145} |ConstructHull|. {149} |AddOne|. {149} |VolumeSign|. {153} |AddOne|: Cube Example. {153} Coplanarity Revisited. {156} |MakeConeFace|. {156} |CleanUp|. {157} 4.3.3 Checks {162} 4.3.4 Performance {162} 4.3.5 Volume Overflow {165} Exercises {168} 4.4 Polyhedral Boundary Representations {170} 4.4.1 Winged-edge Data Structure {170} 4.4.2 Twin-edge Data Structure {171} 4.4.3 Quad-edge Data Structure {171} 4.4.4 Exercises {174} 4.5 Randomized Incremental Algorithm {174} 4.5.1 Exercises {175} 4.6 Higher Dimensions {175} 4.6.1 Coordinates {175} 4.6.2 Hypercube {176} 4.6.3 Regular Polytopes {177} 4.6.4 Hull in Higher Dimensions {177} 4.6.5 Exercises {178} 4.7 Additional Exercises {178} 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 Inte of Halfplanes {193} 5.4.2 Incremental Construction {193} 5.4.3 Divide and Conquer {194} 5.4.4 Fortune's Algorithm {194} Cones {194} Cone Slicing {195} Parabolic Front {197} 5.4.5 Exercises {197} 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 \subseteq {\fam \tw@ D}(P) {204} 5.5.5 Traveling Salesperson Problem {205} 5.5.6 Exercises {208} 5.6 Medial Axis {210} 5.6.1 Exercises {213} 5.7 Connection to Convex Hulls {214} 5.7.1 One-dimensional Delaunay triangulations {214} 5.7.2 Two-dimensional Delaunay triangulations {215} 5.7.3 Implications {219} 5.7.4 Implementation of Delaunay triangulation {219} O(n^4) Code {219} 3D Hull to Delaunay Triangulation: O(n^2) Code {221} 5.7.5 Exercises {221} 5.8 Connection to Arrangements {224} 5.8.1 One-dimensional Voronoi Diagrams {225} 5.8.2 Two-dimensional Voronoi Diagrams {225} 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.4 Three and Higher Dimensions {235} 6.4.1 Exercises {236} 6.5 Duality {236} 6.5.1 Duality mapping {237} 6.5.2 Duality Properties {237} 6.5.3 Exercises {240} 6.6 Higher-Order Voronoi Diagrams {241} 6.6.1 One-Dimensional Diagrams {241} 6.6.2 Two-Dimensional Diagrams {244} 6.6.3 Exercises {245} 6.7 Applications {245} 6.7.1 k-Nearest Neighbors {245} 6.7.2 Hidden Surface Removal {245} 6.7.3 Aspect Graphs {248} 6.7.4 Smallest Polytope Shadow {248} 6.7.5 Exercises {250} 6.7.6 Ham Sandwich Cuts {251} Red-Blue Matching {252} Higher Dimensions {255} 6.7.7 Exercises {255} 6.8 Additional Exercises {255} 7 Search and Intersection 257 7.1 Introduction {257} 7.2 Segment-Segment Intersection {257} 7.3 Segment-Triangle Intersection {261} 7.3.1 Segment-Plane Inte 264 Segment-Plane Implementation {265} Segment-Triangle Classification {269} Barycentric Coordinates. {269} Projection to Two Dimensions. {271} Segment in Plane. {274} Classification by Volumes. {274} 7.3.2 Exercises {278} 7.4 Point in Polygon {279} 7.4.1 Winding number {279} 7.4.2 Ray crossings {280} 7.4.3 Exercises {284} 7.5 Point in Polyhedron {286} Solid Angles {287} Ray Crossings {287} Example: Cube. {291} Example: Nonconvex Polyhedron. {292} 7.5.1 Analysis {292} 7.5.2 Exercises {293} 7.6 Intersection of Convex Polygons {294} 7.6.1 Implementation {298} Special Cases {303} 7.6.2 Exercises {307} 7.7 Intersection of Segments {308} 7.8 Intersection of Nonconvex Polygons {311} 7.8.1 Exercises {313} 7.9 Extreme Point of Convex Polygon {314} 7.9.1 Stabbing a Convex Polygon {316} 7.9.2 Exercises {317} 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.10.6 Exercises {330} 7.11 Planar Point Location {332} 7.11.1 Applications {332} 7.11.2 Independent Set Algorithm {333} 7.11.3 Monotone Subdivisions {333} 7.11.4 Randomized Trapezoidal Decomposition {335} 7.11.5 Exercises {341} 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} 8.5.2 Retraction {371} Voronoi diagram {372} Retraction {373} 8.5.3 Complexity {373} 8.5.4 Exercises {374} 8.6 Robot Arm Motion {376} Problem Definition {376} History {377} 8.6.1 Reachability: Decision {377} Reachability Region {377} Annulus Radii {379} 8.6.2 Reachability: Construction {380} 2-link Reachability {380} 3-link Reachability {381} n-link Reachability {383} Linear Algorithm for n-link Reachability. {383} Two Kinks. {384} Algorithm. {385} 8.6.3 Implementation of Link Configuration {386} Intersection of Two Circles {389} Example {393} 8.6.4 Exercises {394} 8.7 Separability {395} 8.7.1 Varieties of separability {396} 8.7.2 Separability by translation {397} Application {397} Separating segments {398} Separating convex polygons {399} Complexity {399} 8.7.3 Reduction from Partition {400} 8.7.4 Mimicking the Towers of Hanoi {400} 8.7.5 Exercises {402} 9 Sources {405} 9.1 Bibliographies and FAQ's {405} 9.2 Textbooks {406} 9.3 Book Collections {407} 9.4 Monographs {408} 9.5 Journals {408} 9.6 Conference Proceedings {409} 9.7 Software {409} Bibliography {410}