We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of @math points in @math each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish the first deterministic 1.633-approximation algorithm with a time complexity polynomial in both @math and @math . For width, two approximation algorithms are provided: a deterministic @math -approximation running in @math time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact @math -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
@cite_18: Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this article, we study answering range queries over uncertain data. Specifically, we are given a collection P of n uncertain points in ℝ, each represented by its one-dimensional probability density function (pdf). The goal is to build a data structure on P such that, given a query interval I and a probability threshold τ, we can quickly report all points of P that lie in I with probability at least τ. We present various structures with linear or near-linear space and (poly)logarithmic query time. Our structures support pdf's that are either histograms or more complex ones such as Gaussian or piecewise algebraic.
@cite_14: We consider the problem of nearest-neighbor searching among a set of stochastic sites, where a stochastic site is a tuple ((s_i, _i) ) consisting of a point (s_i ) in a (d )-dimensional space and a probability ( _i ) determining its existence. The problem is interesting and non-trivial even in (1 )-dimension, where the Most Likely Voronoi Diagram (LVD) is shown to have worst-case complexity ( (n^2) ). We then show that under more natural and less adversarial conditions, the size of the (1 )-dimensional LVD is significantly smaller: (1) ( (k n) ) if the input has only (k ) distinct probability values, (2) (O(n n) ) on average, and (3) (O(n n ) ) under smoothed analysis. We also present an alternative approach to the most likely nearest neighbor (LNN) search using Pareto sets, which gives a linear-space data structure and sub-linear query time in 1D for average and smoothed analysis models, as well as worst-case with a bounded number of distinct probabilities. Using the Pareto-set approach, we can also reduce the multi-dimensional LNN search to a sequence of nearest neighbor and spherical range queries.
@cite_4: Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for - computing all points that are nearest neighbors of a query point with nonzero probability; and - estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.
@cite_7: 
@cite_8: In this paper, we study the dominance relation under a stochastic setting. Let @math be a set of @math colored stochastic points in @math , each of which is associated with an existence probability. We investigate the problem of computing the probability that a realization of @math contains inter-color dominances, which we call the (CSD) problem. We propose the first algorithm to solve the CSD problem for @math in @math time. On the other hand, we prove that, for @math , even the CSD problem with a restricted color pattern is #P-hard. In addition, even if the existence probabilities are restricted to be @math , the problem remains #P-hard for @math . A simple FPRAS is then provided to approximate the desired probability in any dimension. We also study a variant of the CSD problem in which the dominance relation is considered with respect to not only the standard basis but any orthogonal basis of @math . Specifically, this variant, which we call the free-basis colored stochastic dominance (FBCSD) problem, considers the probability that a realization of @math contains inter-color dominances with respect to any orthogonal basis of @math . We show that the CSD problem is polynomial-time reducible to the FBCSD problem in the same dimension, which proves the #P-hardness of the latter for @math . Conversely, we reduce the FBCSD problem in @math to the CSD problem in @math , by which an @math time algorithm for the former is obtained.
@cite_9: We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points s1,s_2,...,sn in d-dimensional Euclidean space, where each point si is active with some independent and arbitrary but known probability pi. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems is motivated by the uncertainty inherent in many sources of geometric data but has not been investigated before in computational geometry to the best of our knowledge. Our main results include the following. We show that the stochastic MST problem is SPHARD for any dimension d ≥ 2. We present a simple fully polynomial randomized approximation scheme (FPRAS) for a metric space, and thus also for any Euclidean space. For d=2, we present two deterministic approximation algorithms: an O(n4)-time constant-factor algorithm, and a PTAS based on a combination of shifted quadtrees and dynamic programming. We show that in a general metric space the tail bounds of the distribution of the MST length cannot be approximated to any multiplicative factor in polynomial time under the assumption that P ≠ NP. In addition to this existential model of stochastic input, we also briefly consider a locational model where each point is present with certainty but its location is probabilistic.
@cite_2: We describe an @math -time algorithm for computing the exact probability that two @math -dimensional probabilistic point sets are linearly separable, for any fixed @math . A probabilistic point in @math -space is a normal point, but with an associated probability of existence; the existence probabilities of all points are independent. We also show that the @math -dimensional separability problem is equivalent to a @math -dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of @math probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership problem by a factor of @math . In addition, our algorithms can handle input degeneracies in which more than @math points may lie on a @math -dimensional subspace, thus resolving an open problem in 2013. Finally, we prove lower bounds for the separability problem via a reduction from the @math -SUM problem, which show in particular that our @math algorithms for @math -dimensional separability and @math -dimensional convex hull membership are nearly optimal.
@cite_15: Let P be a set of n uncertain points in Red, where each point pi ∈ P is associated with a real value vi and a probability αi ∈ (0,1] of existence, i.e., each pi exists with an independent probability αi. We present algorithms for building an index on P so that for a d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. The specific contributions of our paper include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension d ≥ 1. It also provides a trade-off between query time and size of the index. (ii) A conditional lower bound for the most-likely range-max queries, based on the conjectured hardness of the set-intersection problem, which suggests that in the worst case the product (query time)2 x (index size) is Ω((n2 polylog(n)). (iii) A linear-size index for estimating the expected range-max value within approximation factor 1 2 in O(logc n) time, for some constant c > 0; that is, if the expected maximum value is μ then the query procedure returns a value μ' with μ 2 ≤ μ' ≤ μ. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top-k values of the range-max.
@cite_16: In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint multipoint uncertainty models. Let S=S_R U S_B be a given set of stochastic bichromatic points, and define n = min |S_R|, |S_B| and N = max |S_R|, |S_B| . We show that the separable-probability (SP) of S can be computed in O(nN^ d-1 ) time for d >= 3 and O(min nN log N, N^2 ) time for d=2, while the expected separation-margin (ESM) of S can be computed in O(nN^d) time for d >= 2. In addition, we give an Omega(nN^ d-1 ) witness-based lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and or balls, and extend our algorithms to solve the generalized SP and ESM problems in O(nN^d) and O(nN^ d+1 ) time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.
@cite_10: Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure.
@cite_12: The field of computational geometry is concerned with the design and analysis of geometric algorithms. For such algorithms, correctness and efficiency proofs are constructed, or problems are proven to be hard when no correct and efficient algorithms exist. In order to be able to do this, several assumptions about the input data for geometric algorithms are made. One of them is that this data is correct, with absolute certainty and infinite precision. In practical applications, this is often not the case, and as a result the value of these theoretical guarantees may be questionable. If we want to supply geometric algorithms with theoretical guarantees that are actually observed in practice, we have to loosen our assumptions about the input data to a more realistic level. Depending on the application, we may be confident that each data point, for example, is not more than some value epsilon away from its given position. We can then construct algorithms that are guaranteed to be correct and efficient as long as the input satisfies this weaker assumption. Furthermore, we can analyse how the imprecision in the input influences the accuracy of the output. In this thesis, we present new algorithms for classical geometric problems, that explicitly take data imprecision into account. These algorithms cannot produce the real answers to those problems, but instead produce information about the possible values that the answers can have. In several cases, this can be done without adding any extra cost to the asymptotic running times of the classical solutions. In some cases, though, computing this information is significantly more costly than using classical algorithms, and in some cases we prove that indeed no efficient algorithms exist.
@cite_17: We consider the stochastic geometry model where the location of each node is a random point in a given metric space, or the existence of each node is uncertain. We study the problems of computing the expected lengths of several combinatorial or geometric optimization problems over stochastic points, including closest pair, minimum spanning tree, (k )-clustering, minimum perfect matching, and minimum cycle cover. We also consider the problem of estimating the probability that the length of closest pair, or the diameter, is at most, or at least, a given threshold. Most of the above problems are known to be ( # P )-hard. We obtain FPRAS (Fully Polynomial Randomized Approximation Scheme) for most of them in both the existential and locational uncertainty models. Our result for stochastic minimum spanning trees in the locational uncertain model improves upon the previously known constant factor approximation algorithm. Our results for other problems are the first known to the best of our knowledge.
Geometric computation on uncertain data has received considerable attentions in recent years. A general introduction can be found in @cite_12 . Many fundamental geometric problems have been studied under uncertainty, e.g., nearest-neighbor search @cite_4 @cite_14 , minimum spanning trees @cite_9 , closest pair @cite_17 @cite_7 @cite_10 , range search @cite_18 @cite_15 , linear separability @cite_2 @cite_16 , dominance relation @cite_8 , etc. These problems were studied either under existential uncertainty (which is used in this paper) or under locational uncertainty (where the locations of the data points are uncertain).