Introduction to Computational Geometry

Computational Geometry is a branch of mathematics that deals with the solution of geometric problems that emerge in a variety of applications such as geographic information systems, robotics, and computer graphics, among others. Computational Geometry is covered in depth in this Handbook, which provides an overview of key concepts and results in the field. It can be used as a reference and study aid for those interested in the topic. Not only are the most cutting-edge methods and answers given, but also several alternative approaches to issue solving and problem solving strategies. 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