Source author record

Nirman Kumar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

5works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Robust Proximity Search for Balls using Sublinear Space

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

preprint2014arXiv

Space Exploration via Proximity Search

We investigate what computational tasks can be performed on a point set in $\Re^d$ , if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following: (A) One can compute an approximate bi-criteria $k$ -center clustering of the point set, and more generally compute a greedy permutation of the point set. (B) One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.

preprint2013arXiv

Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space

For a set of $n$ points in $\Re^d$ , and parameters $k$ and $\eps$, we present a data structure that answers $(1+\eps,k)$-\ANN queries in logarithmic time. Surprisingly, the space used by the data-structure is $\Otilde (n /k)$; that is, the space used is sublinear in the input size if $k$ is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this, we provide a sublinear space data-structure that can estimate the density of a point set under various measures, including: \begin{inparaenum}[(i)] \item sum of distances of $k$ closest points to the query point, and \item sum of squared distances of $k$ closest points to the query point. \end{inparaenum} Our approach generalizes to other distance based estimation of densities of similar flavor. We also study the problem of approximating some of these quantities when using sampling. In particular, we show that a sample of size $\Otilde (n /k)$ is sufficient, in some restricted cases, to estimate the above quantities. Remarkably, the sample size has only linear dependency on the dimension.

preprint2013arXiv

Fault Tolerant Clustering Revisited

In discrete k-center and k-median clustering, we are given a set of points P in a metric space M, and the task is to output a set C \subseteq ? P, |C| = k, such that the cost of clustering P using C is as small as possible. For k-center, the cost is the furthest a point has to travel to its nearest center, whereas for k-median, the cost is the sum of all point to nearest center distances. In the fault-tolerant versions of these problems, we are given an additional parameter 1 ?\leq \ell \leq ? k, such that when computing the cost of clustering, points are assigned to their \ell-th nearest-neighbor in C, instead of their nearest neighbor. We provide constant factor approximation algorithms for these problems that are both conceptually simple and highly practical from an implementation stand-point.

preprint2012arXiv

Approximate Nearest Neighbor Search for Low Dimensional Queries

We study the Approximate Nearest Neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high-dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.