Optimal approximate polytope membership

DOI10.1137/1.9781611974782.18MaRDI QIDQ4575755zbMATH OpenOpenAlexFDO

Authors Sunil Arya, David M. Mount, Guilherme D. Da Fonseca

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.01696

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: 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 $qin{R}^d$, it is possible to determine efficiently whether $qinK$. We consider this problem in an approximate setting and assume that $d$ is a constant. Given an approximation parameter $varepsilon>0$, the query can be answered either way if the distance from $q$ to $K$'s boundary is at most $varepsilon$ 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/varepsilo{n}^{d-1})$ storage, whereas storage $O(1/varepsilo{n}^{(d-1)/2})$ admits roughly $O(1/varepsilo{n}^{(d-1)/8})$ query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only $O(1/varepsilo{n}^{(d-1)/2})$, which matches the worst-case lower bound on the complexity of any $varepsilon$-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 $varepsilon$-approximate nearest neighbor queries for a set of $n$ points in $O(logfracnvarepsilon)$ time is reduced to $O(n/varepsilo{n}^{d/2})$. This halves the exponent in the $varepsilon$-dependency of the existing space bound of roughly $O(n/varepsilo{n}^d)$, which has stood for 15 years (Har-Peled, 2001).

Recommendations

• Approximate polytope membership queries
• Approximate polytope membership queries
• Polytope approximation and the Mahler volume
• Near-optimal -kernel construction and related problems
• Polytope membership in high dimension

Cited in

(17)

• Polytope membership in high dimension
• New directions in approximate nearest-neighbor searching
• Near-optimal -kernel construction and related problems
• Approximate polytope membership queries
• Approximate convex intersection detection with applications to width and Minkowski sums
• scientific article; zbMATH DE number 7204982 (Why is no real title available?)
• Economical Delone sets for approximating convex bodies
• Approximate polytope membership queries
• Polytope approximation and the Mahler volume
• Succinct data structures for approximating convex functions with applications
• Economical convex coverings and applications
• Optimal volume-sensitive bounds for polytope approximation
• Ipelets for the convex polygonal geometry (media exposition)
• Improved search of relevant points for nearest-neighbor classification
• Approximate nearest-neighbor search for line segments
• Optimal area-sensitive bounds for polytope approximation
• Farthest-point Voronoi diagrams in the Hilbert metric

This page was built for publication: Optimal approximate polytope membership

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575755)