P. K. Agarwal, S. Har-peled, and K. R. Varadarajan, Approximating extent measures of points, J. Assoc. Comput. Mach, vol.51, pp.606-635, 2004.

P. K. Agarwal, S. Har-peled, and K. R. Varadarajan, Geometric approximation via coresets, Combinatorial and Computational Geometry, 2005.

P. K. Agarwal and J. Matou?ek, 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

N. Alon and J. H. Spencer, The Probabilistic Method, 2000.

S. Arya and T. M. Chan, Better ?-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ?-kernels, Proc. 30th Annu. Sympos, pp.416-425, 2014.

S. Arya, G. D. Da-fonseca, and D. M. Mount, A unified approach to approximate proximity searching, Proc. 18th Annu. European Sympos. Algorithms, pp.374-385, 2010.

S. Arya, G. D. Da-fonseca, and D. M. Mount, Optimal area-sensitive bounds for polytope approximation, Proc. 28th Annu. Sympos, pp.363-372, 2012.
DOI : 10.1145/2261250.2261305

S. Arya, G. D. Da-fonseca, and D. M. Mount, 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

S. Arya, T. Malamatos, and D. M. Mount, Space-time tradeoffs for approximate nearest neighbor searching, J. Assoc. Comput. Mach, vol.57, pp.1-54, 2009.

S. Arya and D. M. Mount, Approximate range searching, Comput. Geom. Theory Appl, vol.17, pp.135-163, 2000.
DOI : 10.1145/220279.220298

K. Ball, An elementary introduction to modern convex geometry, Flavors of Geometry, vol.31, pp.1-58, 1997.

L. Barba and S. Langerman, Optimal detection of intersections between convex polyhedra, Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.1641-1654, 2015.

G. Barequet and S. Har-peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, J. Algorithms, vol.38, pp.91-109, 2001.

J. L. Bentley, M. G. Faust, and F. P. Preparata, Approximation algorithms for convex hulls, Commun. ACM, vol.25, issue.1, pp.64-68, 1982.
DOI : 10.1145/358315.358392

J. Bourgain and V. D. Milman, New volume ratio properties for convex symmetric bodies. Inventiones Mathematicae, vol.88, pp.319-340, 1987.
DOI : 10.1007/bf01388911

E. M. Bronshteyn and L. D. Ivanov, The approximation of convex sets by polyhedra, Siberian Math. J, vol.16, pp.852-853, 1976.

E. M. Bronstein, Approximation of convex sets by polytopes, Journal of Mathematical Sciences, vol.153, issue.6, pp.727-762, 2008.

C. J. Burges, A tutorial on support vector machines for pattern recognition, Data Min. Knowl. Discov, vol.2, issue.2, pp.121-167, 1998.

T. M. Chan, Fixed-dimensional linear programming queries made easy, Proc. 12th Annu. Sympos, pp.284-290, 1996.

T. M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Discrete Comput. Geom, vol.16, pp.369-387, 1996.

T. M. Chan, Closest-point problems simplified on the RAM, Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.472-473, 2002.

T. M. Chan, Faster core-set constructions and data-stream algorithms in fixed dimensions, Comput. Geom. Theory Appl, vol.35, issue.1, pp.20-35, 2006.

T. M. Chan, Optimal partition trees, Proc. 26th Annu. Sympos, pp.1-10, 2010.

B. Chazelle and D. P. Dobkin, Intersection of convex objects in two and three dimensions, J. Assoc. Comput. Mach, vol.34, pp.1-27, 1987.

B. Chazelle and J. Matou?ek, On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, vol.21, pp.579-597, 1996.

K. L. Clarkson, Algorithms for polytope covering and approximation, Proc. Third Internat. Workshop Algorithms Data Struct, pp.246-252, 1993.

K. L. Clarkson, An algorithm for approximate closest-point queries, Proc. Tenth Annu. Sympos, pp.160-164, 1994.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2001.

M. De-berg, O. Cheong, M. Van-kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, 2010.

D. P. Dobkin and D. G. Kirkpatrick, Fast detection of polyhedral intersection, Theo. Comp. Sci, vol.27, pp.241-253, 1983.

R. M. Dudley, Metric entropy of some classes of sets with differentiable boundaries, Approx. Theory, vol.10, issue.3, pp.227-236, 1974.

C. A. Duncan, M. T. Goodrich, and S. Kobourov, Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees, J. Algorithms, vol.38, pp.303-333, 2001.

H. Edelsbrunner, Algorithms in Combinatorial Geometry, 1987.

H. G. Eggleston and . Convexity, , 1958.

J. Erickson, L. J. Guibas, J. Stolfi, and L. Zhang, Separation-sensitive collision detection for convex objects, Proc. Tenth Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.327-336, 1999.

P. M. Gruber, Asymptotic estimates for best and stepwise approximation of convex bodies I, Forum Math, vol.5, pp.521-537, 1993.

S. Har-peled, A replacement for Voronoi diagrams of near linear size, Proc. 42nd Annu, pp.94-103, 2001.

S. Har-peled, Geometric Approximation Algorithms, 2011.
DOI : 10.1090/surv/173

URL : http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/book.pdf

J. K. Boroczky, Approximation of general smooth convex bodies, Adv. Math, vol.153, pp.325-341, 2000.

G. Kuperberg, From the Mahler conjecture to Gauss linking integrals, Geometric And Functional Analysis, vol.18, pp.870-892, 2008.

J. Matou?ek and O. Schwarzkopf, On ray shooting in convex polytopes, Discrete Comput. Geom, vol.10, pp.215-232, 1993.

J. Matou?ek, Reporting points in halfspaces, Comput. Geom. Theory Appl, vol.2, pp.169-186, 1992.

J. Matou?ek, Linear optimization queries, J. Algorithms, vol.14, issue.3, pp.432-448, 1993.

J. Matou?ek, Lectures on Discrete Geometry, 2002.

J. S. Mitchell and S. Suri, Separation and approximation of polyhedral objects, Comput. Geom. Theory Appl, vol.5, pp.95-114, 1995.

E. A. Ramos, Linear programming queries revisited, Proc. 16th Annu. Sympos, pp.176-181, 2000.
DOI : 10.1145/336154.336198

Y. Sabharwal, S. Sen, and N. Sharma, Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, J. Comput. Sys. Sci, vol.72, pp.955-977, 2006.

L. A. Santaló, 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)