Approximate Polytope Membership Queries
DOI10.1137/16M1061096zbMath1381.52019OpenAlexW3102249523MaRDI QIDQ4600697
David M. Mount, Sunil Arya, Guilherme Dias da Fonseca
Publication date: 12 January 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1061096
approximation algorithmsMahler volumeconvex approximationnearest neighbor searchingspace-time trade-offsgeometric retrievalpolytope membership
(n)-dimensional polytopes (52B11) Multidimensional problems (41A63) Convexity of real functions in one variable, generalizations (26A51) Data structures (68P05) Approximation algorithms (68W25) Approximation by convex sets (52A27) Approximation by arbitrary linear expressions (41A45)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On ray shooting in convex polytopes
- Fast detection of polyhedral intersection
- From the Mahler conjecture to Gauss linking integrals
- Reporting points in halfspaces
- The approximation of convex sets by polyhedra
- Approximation of general smooth convex bodies
- Approximate range searching
- Output-sensitive results on convex hulls, extreme points, and related problems
- New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
- Separation and approximation of polyhedral objects
- Metric entropy of some classes of sets with differentiable boundaries
- Faster core-set constructions and data-stream algorithms in fixed dimensions
- Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
- Approximation of convex sets by polytopes
- Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
- Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees
- Optimal area-sensitive bounds for polytope approximation
- Approximating extent measures of points
- Ray Shooting and Parametric Search
- Space-time tradeoffs for approximate nearest neighbor searching
- A Unified Approach to Approximate Proximity Searching
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Approximation algorithms for convex hulls
- Asymptotic estimates for best and stepwise approximation of convex bodies II
- Optimal Approximate Polytope Membership
- Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels
- Linear Optimization Queries
- Algorithms for polytope covering and approximation
- Linear programming queries revisited
- Optimal detection of intersections between convex polyhedra
- Optimal partition trees
- Approximate polytope membership queries
This page was built for publication: Approximate Polytope Membership Queries
