Optimal Approximate Polytope Membership - Université Clermont Auvergne Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Optimal Approximate Polytope Membership

Sunil Arya
  • Fonction : Auteur
  • PersonId : 1037255
David M Mount
  • Fonction : Auteur
  • PersonId : 1037256

Résumé

In the polytope membership problem, a convex polytope K in R^d is given, and the objective is to preprocess K into a data structure so that, given a query point q ∈ R^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 trade-off, 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 (Har-Peled, 2001).
Fichier principal
Vignette du fichier
membership.pdf (465.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01893784 , version 1 (11-10-2018)

Identifiants

Citer

Sunil Arya, Guilherme da Fonseca, David M Mount. Optimal Approximate Polytope Membership. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2017, Barcelona, Spain. ⟨10.1137/1.9781611974782.18⟩. ⟨hal-01893784⟩
12 Consultations
52 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More