Shape Fitting on Point Sets with Probability Distributions

A typical computational geometry problem begins: Consider a set $P$ of $n$ points in $R^d$. However, many applications today work with input that is not precisely known, for example when the data is sensed and has some known error model. What if we do not know the set $P$ exactly, but rather we have a probability distribution governing the location of each point $p$ in $P$? Consider a set of (non-fixed) points $P$. We study several measures (e.g. the radius of the smallest enclosing ball, or the area of the smallest enclosing box) with respect to this distribution. The solutions to these problems do not, as in the traditional case, consist of a single answer, but rather a distribution of answers. We hence describe a data structure, called an $-quantization, that can approximate such a distribution within $ in $O(1/$ space. We also extend this data structure to answer higher dimensional queries (e.g. the length and width of the smallest enclosing box in $R^2$). Rather than compute a new data structure for each measure we are interested in, we can also compute a single data structure that allows us to answer many questions at once. This data structure, an $( $-kernel, is based on $-kernel coresets and can be used to create approximate $-quantizations for geometric problems involving extent measures. Thirdly, we introduce a data structure that can answer questions of the type 'what is the probability that point $q$ is in the smallest enclosing ball of $P$?' For a given distribution and summarizing shape (e.g. the smallest enclosing ball), we define an $-shape inclusion probability function to be a function that assigns to a query point $q$ in $R^d$ a value that is at most $ away from the probability that $q$ is contained in this summarizing shape of $P$. This results in a probability description more directly linked to the space that the input points live in. We provide simple and efficient randomized algorithms for computing all of these data structures, which are easy to implement and practical. We provide some experimental results to assert this.