Approximate polytope membership queries

DOI10.1137/16M1061096zbMATH Open1381.52019OpenAlexW3102249523MaRDI QIDQ4600697FDOQ4600697

Authors: Sunil Arya, David M. Mount, Guilherme D. 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

Recommendations

• Approximate polytope membership queries
• Optimal approximate polytope membership
• Polytope approximation and the Mahler volume
• Polytope membership in high dimension
• scientific article; zbMATH DE number 437552

zbMATH Keywords

approximation algorithmsMahler volumeconvex approximationnearest neighbor searchingspace-time trade-offsgeometric retrievalpolytope membership

Mathematics Subject Classification ID

Data structures (68P05) Multidimensional problems (41A63) Approximation algorithms (68W25) (n)-dimensional polytopes (52B11) Convexity of real functions in one variable, generalizations (26A51) Approximation by convex sets (52A27) Approximation by arbitrary linear expressions (41A45)

Cites Work

• Introduction to algorithms
• New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• Separation and approximation of polyhedral objects
• Approximating extent measures of points.
• Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
• From the Mahler conjecture to Gauss linking integrals
• Title not available (Why is that?)
• Approximation of general smooth convex bodies
• Geometric approximation algorithms
• Algorithms for polytope covering and approximation
• Title not available (Why is that?)
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Title not available (Why is that?)
• Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
• Approximation of convex sets by polytopes
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On ray shooting in convex polytopes
• Reporting points in halfspaces
• Output-sensitive results on convex hulls, extreme points, and related problems
• Balanced aspect ratio trees: Combining the advantages of \(k\)-\(d\) trees and octrees
• Linear Optimization Queries
• Title not available (Why is that?)
• Linear programming queries revisited
• Optimal partition trees
• Optimal detection of intersections between convex polyhedra
• The approximation of convex sets by polyhedra
• Ray Shooting and Parametric Search
• Asymptotic estimates for best and stepwise approximation of convex bodies II
• Metric entropy of some classes of sets with differentiable boundaries
• Optimal area-sensitive bounds for polytope approximation
• Fast detection of polyhedral intersection
• Approximation algorithms for convex hulls
• A unified approach to approximate proximity searching
• Title not available (Why is that?)
• Approximate range searching
• Space-time tradeoffs for approximate nearest neighbor searching
• Approximate polytope membership queries
• Optimal Approximate Polytope Membership
• Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Cited In (4)

• The \(\varepsilon\)-\(t\)-net problem
• Succinct data structures for approximating convex functions with applications
• Coresets for the Nearest-Neighbor Rule
• Title not available (Why is that?)

This page was built for publication: Approximate polytope membership queries

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