Search

Classical computational geometry algorithms handle geometric constructs whose shapes and locations are exact. However, many real-world applications require modeling and computing with geometric uncertainties, which are often coupled and mutually dependent. In this paper we address the relative position of points, point set distance problems, and orthogonal range queries in the plane in the presence of geometric uncertainty. The uncertainty can be in the locations of the points, in the query range, or both, and is possibly coupled. Point coordinates and range uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), a general and computationally efficient worst-case, first-order linear approximation of geometric uncertainty that supports dependence among uncertainties. We present efficient algorithms for relative points orientation, minimum and maximum pairwise distance, closest pair, diameter, and efficient algorithms for uncertain range queries: uncertain range/nominal points, nominal range/uncertain points, uncertain range/uncertain points, with independent/dependent uncertainties. In most cases, the added complexity is sub-quadratic in the number of parameters and points, with higher complexities for dependent point uncertainties. [ABSTRACT FROM AUTHOR]

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network GS with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]