Introduction to Computational Geometry

Cover
HalfTitle Page
Title Page
Copyright
About the Author
Table of Contents
List of Figures
List of Tables
List of Abbreviations
Preface
Chapter 1: Fundamentals of Computational Geometry
	1.1. Introduction
	1.2. Computing
	1.3. An Example: Convex Hulls
	1.4. Degeneracies and Robustness
	1.5. Application Domains
	References
Chapter 2: Polygon Triangulation
	2.1. Introduction
	2.2. Guarding and Triangulations
	2.3. Partitioning A Polygon Into Monotone Pieces
	2.4. Triangulating A Monotone Polygon
	References
Chapter 3: Fundamentals of Line Segment Intersection
	3.1. Introduction
	3.2. Line Segment Intersection
	3.3. The Doubly-connected Edge List
	3.4. Computing the Overlay of Two Subdivisions
	3.5. Boolean Operations
	References
Chapter 4: Computational Geometry and Linear Programming
	4.1. Introduction
	4.2. The Geometry of Casting
	4.3. Half-plane Intersection
	4.4. Prune-and-search Model and Its Application To 2d Linear Programming
	4.5. Linear L1 Approximation of Points
	4.6. A Randomized Algorithm for Linear Programming
	4.7. Linear Programming in Mathematical Programming
	4.8. Multiplicative Penalty Function Technique For Linear Programming
	References
Chapter 5: Uses of Computational Geometry in Geographic Information Systems
	5.1. Introduction
	5.2. Map Data Modeling
	5.3. Map Data Processing
	5.4. Terrain Data Modeling and Processing
	5.5. Three-dimensional GIS
	References
Chapter 6: Robot Motion Planning
	6.1. Introduction
	6.2. Work Space and Configuration Space
	6.3. Point Robots
	6.4. Minkowski Sums
	6.5. Translational Motion Planning
	6.6. Motion Planning With Rotations
	References
Chapter 7: Application of Computational Geometry in Computer Graphics
	7.1. Introduction
	7.2. Representing Subdivisions of Plane and Space
	7.3. The Basic Techniques in Computer Graphics
	References
Chapter 8: Computational Geometry in Graph Drawing
	8.1. Introduction
	8.2. Types of Graphs
	8.3. Types of Drawings
	8.4. Properties of Drawings
	8.5. Bounds
	8.6. Tradeoff Between Area and Aspectratio
	8.7. Methods For Drawing Graphs
	References
Index
Back Cover