Computational Geometry with Independent and Dependent Uncertainties

Description

Contents Preface About the Authors Acknowledgments 1. Introduction 1.1 Background 1.2 Literature Review 1.2.1 Deterministic models 1.2.2 Probabilistic models 1.2.3 Topological stability 1.2.4 The linear parametric geometric uncertainty model 1.3 Goals 1.4 Overview and Novelty 1.4.1 Uncertainty zone 1.4.2 Half-plane point retrieval queries 1.4.3 Euclidean minimum spanning trees 1.4.4 Voronoi diagram and Delaunay triangulation 1.5 Book Organization 2. The Linear Parametric Geometric Uncertainty Model 2.1 Basic Definitions 2.2 LPGUM Coordinate 2.3 LPGUM Point and Vector 2.4 LPGUM Line and Edge 2.5 LPGUM Three-Point Circle 2.6 Summary 3. The Envelopes of Uncertain Points, Lines and Circles 3.1 LPGUM Coordinate and Point 3.2 LPGUM Line 3.2.1 Definitions and properties 3.2.2 Cone diagram mapping: Definition and properties 3.2.3 LPGUM line envelope algorithm 3.3 LPGUM Three-Point Circle 3.3.1 LPGUM three-point circle spanning the plane 3.3.2 The outer envelope of an independent LPGUM three-point circle 3.3.3 Algorithm to compute the outer envelope of an independent LPGUM three-point circle 3.3.3.1 Smallest three-point enclosing circle 3.3.3.2 Circle tangent to an edge or to one of its vertices test 3.3.3.3 Outer envelope of an LPGUM three-point circle 3.4 Summary 4. Half-Plane Point Retrieval Queries 4.1 Background 4.2 Half-Plane Point Retrieval Queries 4.2.1 Exact line and exact points 4.2.2 Exact line and LPGUM points 4.2.3 LPGUM line and exact points 4.2.4 LPGUM line and LPGUM points with no mutual dependencies 4.2.5 Dependent LPGUM line and LPGUM points with dependencies between them 4.3 Summary 5. Euclidean Minimum Spanning Trees 5.1 Background 5.2 Uncertain EMST: Definitions and Properties 5.3 Pairwise Uncertain Edge Weight Comparison 5.3.1 Independent case 5.3.2 Dependent case 5.4 Uncertain EMST Stability Test 5.4.1 Stability test for independent and dependent cases 5.4.1.1 Independent case 5.4.1.2 Dependent case 5.4.2 Stability test with lower complexity for the independent case 5.4.3 Recursive stability test for the independent case 5.5 The Weight of an Uncertain EMST 5.6 Summary 6. Voronoi Diagram and Delaunay Triangulation 6.1 Background 6.2 Voronoi Diagram and Delaunay Triangulation of LPGUM Points 6.2.1 Definitions and properties 6.2.2 Uncertain Voronoi diagram equivalence and stability 6.3 LPGUM Bisectors 6.4 Intersection of Two Independent LPGUM Lines 6.5 Properties of an Independent Uncertain Voronoi Diagram Vertex 6.6 Stable Uncertain Voronoi Diagram Construction 6.6.1 Algorithm 6.6.2 Uncertain Voronoi vertex computation 6.6.3 Uncertain Voronoi edge computation 6.6.4 Uncertain Voronoi face computation 6.7 Point Location Queries in a Stable Uncertain Voronoi Diagram 6.7.1 Exact point location query 6.7.1.1 Nominal Voronoi diagram 6.7.1.2 Uncertain Voronoi diagram 6.7.1.3 Extended trapezoidal map (Independent case) 6.7.2 Uncertain point location query 6.8 Dynamic Stable Uncertain Voronoi Diagram 6.9 Summary 7. Conclusion 7.1 Summary 7.2 Open Problems References Index