Robust Proximity Search for Balls Using Sublinear Space

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalArticlepeer-review


Given a set of n disjoint balls b1, ⋯ , bn in IRd, we provide a data structure of near linear size that can answer (1 ± ε) -approximate kth-nearest neighbor queries on the balls in O(log n+ 1 / εd) time, where k and ε may be provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.

Original languageEnglish (US)
Pages (from-to)279-299
Number of pages21
Issue number1
StatePublished - Jan 1 2018


  • Approximation algorithms
  • Data structures
  • Proximity search

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Robust Proximity Search for Balls Using Sublinear Space'. Together they form a unique fingerprint.

Cite this