Arrow Research search

Author name cluster

David M. Mount

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers
1 author row

Possible papers

25

SODA Conference 2019 Conference Paper

Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances

  • Ahmed Abdelkader
  • Sunil Arya
  • Guilherme Dias da Fonseca
  • David M. Mount

We present a new approach to ε -approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance. As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry. We are given n points in ℝ d, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O ( n log(1/ ε )/ ε d /2 ) space, which nearly matches the best known results for the Euclidean metric.

Details

SODA Conference 2017 Conference Paper

Optimal Approximate Polytope Membership

  • Sunil Arya
  • Guilherme Dias da Fonseca
  • David M. Mount

In the polytope membership problem, a convex polytope K in ℝ d is given, and the objective is to preprocess K into a data structure so that, given a query point q ∊ ℝ d, it is possible to determine efficiently whether q ∊ K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter ∊ > 0, the query can be answered either way if the distance from q to K's boundary is at most ∊ times K's diameter. Previous solutions to the problem were on the form of a space-time tradeoff, where logarithmic query time demands O (1/∊ d-1 ) storage, whereas storage O (1/∊ (d-1)/2 ) admits roughly O (1/∊ (d-1)/8 ) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O (1/∊ ( d -1)/2 ), which matches the worst-case lower bound on the complexity of any ∊- approximating polytope. Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer ∊-approximate nearest neighbor queries for a set of n points in O (log n/∊ ) time is reduced to O ( n /∊ d /2 ). This halves the exponent in the ∊-dependency of the existing space bound of roughly O ( n /∊ d ), which has stood for 15 years (HarPeled, 2001).

Details

SODA Conference 2016 Conference Paper

A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees

  • Sunil Arya
  • David M. Mount

The Euclidean minimum spanning tree (EMST) is a fundamental and widely studied structure. In the approximate version we are given an n -element point set P in ℝ d and an error parameter ∊ > 0, and the objective is to compute a spanning tree over P whose weight is at most (1 + ∊ ) times that of the true minimum spanning tree. Assuming that d is a fixed constant, existing algorithms have running times that (up to logarithmic factors) grow as O( n / ∊ Ω( d ) ). We present an algorithm whose running time is. Thus, this is the first algorithm for approximate EMSTs that eliminates the exponential ∊ dependence on dimension. (Note that the O -notation conceals a constant factor of the form O (1) d.) The algorithm is deterministic and very simple.

Details

SODA Conference 2012 Conference Paper

Polytope approximation and the Mahler volume

  • Sunil Arya
  • Guilherme Dias da Fonseca
  • David M. Mount

The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in R d, the objective is to minimize the number of vertices (alternatively the number of facets) of an approximating polytope for a given Hausdorff error ε. Results to date have been of two types. The first type assumes that K is smooth, and bounds hold in the limit as ε tends to zero. The second type requires no such assumptions. The latter type includes the well known results of Dudley (1974) and Bronshteyn and Ivanov (1976), which show that in spaces of fixed dimension, O ((diam( K )/ε) ( d − 1)/2 ) vertices (alt. , facets) suffice. Our results are of this latter type. In our first result, under the assumption that the width of the body in any direction is at least ε, we strengthen the above bound to. This is never worse than the previous bound (by more than logarithmic factors) and may be significantly better for skinny bodies. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume. This is a dimensionless quantity that involves the product of the volumes of a convex body and its polar dual. In our second result, we apply the same machinery to improve upon the best known bounds for answering ε-approximate polytope membership queries. Given a convex polytope P defined as the intersection of halfspaces, such a query determines whether a query point q lies inside or outside P, but may return either answer if q 's distance from P 's boundary is at most ε. We show that, without increasing storage, it is possible to reduce the best known search times for ε-approximate polytope membership significantly. This further implies improvements to the best known search times for approximate nearest neighbor searching in spaces of fixed dimension.

Details

STOC Conference 2006 Conference Paper

On the importance of idempotence

  • Sunil Arya
  • Theocharis Malamatos
  • David M. Mount

Range searching is among the most fundamental problems in computational geometry. An n-element point set in R d is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω * (n 2/5 ) lower bound for integral semigroups, improving upon the best lower bound of Ω * (n 1/3 ), thus closing the gap with the O(n 1/2 ) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.

Details

FOCS Conference 2000 Conference Paper

Nearly Optimal Expected-Case Planar Point Location

  • Sunil Arya
  • Theocharis Malamatos
  • David M. Mount

We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell.

Details

FOCS Conference 1994 Conference Paper

Randomized and deterministic algorithms for geometric spanners of small diameter

  • Sunil Arya
  • David M. Mount
  • Michiel H. M. Smid

Let S be a set of n points in IR/sup d/ and let t>1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions. >

Details

FOCS Conference 1987 Conference Paper

An Output Sensitive Algorithm for Computing Visibility Graphs

  • Subir Kumar Ghosh
  • David M. Mount

The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertices are the vertices of the obstacles and whose edges are pairs of vertices (u, v) such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. An algorithm is presented that computes the visibility graph of s set of obstacles in time O(E + n log n), where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles.

Details