Computational Geometry with Independent and Dependent Uncertainties

The following sections are included:

• Dedication
• Preface
• About the Authors
• Acknowledgments
• Contents

Geometric uncertainty is ubiquitous in mechanical CAD/CAM, robotics, computer vision, wireless networks and many other fields. Sensing, localization, measurement and manufacturing processes are intrinsically imprecise, and thereby introduce error and uncertainty. In contrast, the corresponding geometric models are usually exact and do not account for these inaccuracies. Modeling and computing geometric variability and its consequences are thus of great scientific, technical and economic importance…

This chapter presents the Linear Parametric Geometric Uncertainty Model (LPGUM) and the basic LPGUM geometric entities. Section 2.1 presents basic definitions. Section 2.2 presents the LPGUM coordinate. Section 2.3 presents the LPGUM point, vector and point set. Section 2.4 presents the LPGUM line and edges. Section 2.5 presents the LPGUM three-point circle. Section 2.6 summarizes the properties and characteristics of the LPGUM.

This chapter describes algorithms for computing the uncertainty envelopes of elementary geometric entities: coordinates, points, lines and circles. Section 3.1 presents methods for computing the envelope of the LPGUM coordinate and point. Section 3.2 describes the properties of the envelope of the an LPGUM line and presents a new algorithm for computing it. Section 3.3 presents the properties of the envelope of the LPGUM three-point circle and an efficient algorithm for computing it. Section 3.4 summarizes this chapter.

This chapter addresses a family of geometric half-plane retrieval queries of points in the plane in the presence of geometric uncertainty. The problems include exact and uncertain point sets and half-plane queries defined by an exact or uncertain line. Section 4.1 introduces the problem. Section 4.2 defines the half-plane retrieval queries and presents algorithms for answering them. Section 4.3 summarizes the results of this chapter.

This chapter addresses the problems of constructing the Euclidean minimum spanning tree (EMST) of points in the plane with mutually dependent location uncertainties, testing its stability and computing its total weight. Section 5.1 introduces the problem and reviews the relevant literature. Section 5.2 defines the uncertain EMST of a set of LPGUM points and its properties. Section 5.3 presents algorithms for comparison of uncertain Euclidean graph edge weights. Section 5.4 describes algorithms for testing the stability of an uncertain EMST. Section 5.5 describes a method for computing the minimum and maximum weight of a stable uncertain EMST. Section 5.6 summarizes this chapter.

This chapter addresses the problems of constructing the Voronoi diagram (VD) and Delaunay triangulation (DT) of points in the plane with mutually dependent location uncertainties. Section 6.1 presents the background. Section 6.2 defines an uncertain VD and uncertain DT. Section 6.3 defines the LPGUM bisector. Section 6.4 describes the intersection of two LPGUM lines. Section 6.5 defines the uncertain VD vertex. Section 6.6 describes an efficient algorithm for computing a stable uncertain VD. Section 6.7 describes the exact and uncertain LPGUM point location queries. Section 6.8 describes how to efficiently update a stable uncertain VD by inserting or deleting an LPGUM point. Section 6.9 summarizes the results.

This chapter concludes the book and presents several open problems.

The following sections are included:

• References
• Index