## Abstract

Given a (master) set M of n points in d-dimensional Euclidean space, consider drawing a random subset that includes each point ^{mi}â̂̂M with an independent probability ^{pi}. How difficult is it to compute elementary statistics about the closest pair of points in such a subset? For instance, what is the probability that the distance between the closest pair of points in the random subset is no more than ℓ, for a given value ℓ? Or, can we preprocess the master set M such that given a query point q, we can efficiently estimate the expected distance from q to its nearest neighbor in the random subset? These basic computational geometry problems, whose complexity is quite well-understood in the deterministic setting, prove to be surprisingly hard in our stochastic setting. We obtain hardness results and approximation algorithms for stochastic problems of this kind.

Original language | English (US) |
---|---|

Pages (from-to) | 214-223 |

Number of pages | 10 |

Journal | Computational Geometry: Theory and Applications |

Volume | 47 |

Issue number | 2 PART A |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

## Keywords

- Approximation algorithms
- Computational geometry
- Data structures
- Probabilistic optimization

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics