Computational Geometry in C (2nd Ed.)
Table of Contents (Detailed)
(Page numbers in braces only approximate.)
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}