Closest pair and the post office problem for stochastic points

Pegah Kamousi, Timothy M. Chan, Subhash Suri

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)214-223
Number of pages10
JournalComputational Geometry: Theory and Applications
Volume47
Issue number2 PART A
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Closest pair and the post office problem for stochastic points'. Together they form a unique fingerprint.

Cite this