Approximating extent measures of points, J. Assoc. Comput. Mach, vol.51, pp.606-635, 2004. ,
Geometric approximation via coresets, Combinatorial and Computational Geometry, 2005. ,
Ray shooting and parametric search, SIAM J. Comput, vol.22, issue.4, pp.794-806, 1993. ,
DOI : 10.1137/0222051
URL : http://www.cs.duke.edu/~pankaj/publications/papers/query-ps.pdf
The Probabilistic Method, 2000. ,
Better ?-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ?-kernels, Proc. 30th Annu. Sympos, pp.416-425, 2014. ,
A unified approach to approximate proximity searching, Proc. 18th Annu. European Sympos. Algorithms, pp.374-385, 2010. ,
Optimal area-sensitive bounds for polytope approximation, Proc. 28th Annu. Sympos, pp.363-372, 2012. ,
DOI : 10.1145/2261250.2261305
Optimal approximate polytope membership, Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.270-288, 2017. ,
DOI : 10.1137/1.9781611974782.18
URL : https://hal.archives-ouvertes.fr/hal-01893784
Space-time tradeoffs for approximate nearest neighbor searching, J. Assoc. Comput. Mach, vol.57, pp.1-54, 2009. ,
Approximate range searching, Comput. Geom. Theory Appl, vol.17, pp.135-163, 2000. ,
DOI : 10.1145/220279.220298
An elementary introduction to modern convex geometry, Flavors of Geometry, vol.31, pp.1-58, 1997. ,
Optimal detection of intersections between convex polyhedra, Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.1641-1654, 2015. ,
Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, J. Algorithms, vol.38, pp.91-109, 2001. ,
Approximation algorithms for convex hulls, Commun. ACM, vol.25, issue.1, pp.64-68, 1982. ,
DOI : 10.1145/358315.358392
, New volume ratio properties for convex symmetric bodies. Inventiones Mathematicae, vol.88, pp.319-340, 1987.
DOI : 10.1007/bf01388911
The approximation of convex sets by polyhedra, Siberian Math. J, vol.16, pp.852-853, 1976. ,
Approximation of convex sets by polytopes, Journal of Mathematical Sciences, vol.153, issue.6, pp.727-762, 2008. ,
A tutorial on support vector machines for pattern recognition, Data Min. Knowl. Discov, vol.2, issue.2, pp.121-167, 1998. ,
Fixed-dimensional linear programming queries made easy, Proc. 12th Annu. Sympos, pp.284-290, 1996. ,
Output-sensitive results on convex hulls, extreme points, and related problems, Discrete Comput. Geom, vol.16, pp.369-387, 1996. ,
Closest-point problems simplified on the RAM, Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.472-473, 2002. ,
Faster core-set constructions and data-stream algorithms in fixed dimensions, Comput. Geom. Theory Appl, vol.35, issue.1, pp.20-35, 2006. ,
Optimal partition trees, Proc. 26th Annu. Sympos, pp.1-10, 2010. ,
Intersection of convex objects in two and three dimensions, J. Assoc. Comput. Mach, vol.34, pp.1-27, 1987. ,
On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, vol.21, pp.579-597, 1996. ,
Algorithms for polytope covering and approximation, Proc. Third Internat. Workshop Algorithms Data Struct, pp.246-252, 1993. ,
An algorithm for approximate closest-point queries, Proc. Tenth Annu. Sympos, pp.160-164, 1994. ,
Introduction to Algorithms, 2001. ,
, Computational Geometry: Algorithms and Applications, 2010.
Fast detection of polyhedral intersection, Theo. Comp. Sci, vol.27, pp.241-253, 1983. ,
Metric entropy of some classes of sets with differentiable boundaries, Approx. Theory, vol.10, issue.3, pp.227-236, 1974. ,
Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees, J. Algorithms, vol.38, pp.303-333, 2001. ,
Algorithms in Combinatorial Geometry, 1987. ,
, , 1958.
Separation-sensitive collision detection for convex objects, Proc. Tenth Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.327-336, 1999. ,
Asymptotic estimates for best and stepwise approximation of convex bodies I, Forum Math, vol.5, pp.521-537, 1993. ,
A replacement for Voronoi diagrams of near linear size, Proc. 42nd Annu, pp.94-103, 2001. ,
Geometric Approximation Algorithms, 2011. ,
DOI : 10.1090/surv/173
URL : http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/book.pdf
Approximation of general smooth convex bodies, Adv. Math, vol.153, pp.325-341, 2000. ,
From the Mahler conjecture to Gauss linking integrals, Geometric And Functional Analysis, vol.18, pp.870-892, 2008. ,
On ray shooting in convex polytopes, Discrete Comput. Geom, vol.10, pp.215-232, 1993. ,
Reporting points in halfspaces, Comput. Geom. Theory Appl, vol.2, pp.169-186, 1992. ,
Linear optimization queries, J. Algorithms, vol.14, issue.3, pp.432-448, 1993. ,
Lectures on Discrete Geometry, 2002. ,
Separation and approximation of polyhedral objects, Comput. Geom. Theory Appl, vol.5, pp.95-114, 1995. ,
Linear programming queries revisited, Proc. 16th Annu. Sympos, pp.176-181, 2000. ,
DOI : 10.1145/336154.336198
Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, J. Comput. Sys. Sci, vol.72, pp.955-977, 2006. ,
An affine invariant for convex bodies of n-dimensional space, Portugaliae Mathematica, vol.8, pp.155-161, 1949. ,
, The following range spaces (X i , R i ) have constant VC-dimension (where the constant depends only on d): (1) X 1 = ?K and R 1 is the set of ?-dual caps. (2) X 2 = S and R 2 is the set of Voronoi patches of the ?-dual caps. (3) X 3 = ?K and R 3 is the set of ?-restricted ?-dual caps, A Omitted Proofs Lemma 5.3. Let K be a convex body in R d that lies within Q 0 , and let ? and ? be positive real parameters
, Under the polar transformation (recall Section 2.3), these supporting hyperplanes are mapped to a set of points that form the boundary of polar(K), which is a convex body. Consider any point q that is external to K (see Figure 26(a)). If we treat q as a vector, We may assume that K contains the origin, since this clearly does not affect the VC-dimension of these range spaces
, By the inclusion-reversing properties of the polar, the points of this cap are in 1-1 correspondence with the supporting hyperplanes of K that separate q from K. It follows that the set of dual caps of K is equivalent, through polarity, to the set of caps of polar(K). The range space of caps is equivalent to the range space of halfspaces, Consider the cap of polar(K) induced by polar(q)