, The SCC of the dual set system induced by objects with union complexity ? is??is? is??(m) = O(?(m)/m), which together with Theorem 3 implies the stated bound. The value of ?(m) is O(m) for triangles with approximately same size [80], O(m log * m) for ?-fat triangles [48](where the constant of proportionality depends only on ?), and O(m2 log * m ) for locally ?-fat objects, Remember that the dual of a semi-algebraic set system is itself semi-algebraic (Lemma 1.3)

, R) be the set system induced on a set X of n points in R 2 by the family of axis-parallel rectangles. Aronov, Ezra, and Sharir [10] show that there is another set system R on X with SCC ? R (m, l) = O (l · log m)

, The other results follow from the facts that the SCC ?(m, l) ? of the primal set system induced on R 2 is O(m) for lines, O(ml) for strips, and O(ml 2 ) for cones, vol.86

, Macbeath Regions [1, +?). Perhaps some kind of interpolation could be defined on grid graphs of distinct dimensions, ? of the primal set system induced on R 2 by pseudodisks is

, ? Describe the exchange graphs for Terrain Guarding (see page 96). Can our lower bound construction be adapted to this problem?

, Prove the conjecture on page 97: the correct value of c 5 (the left-to-right ratio for planar 5-expanding graphs) is 3. More generally, determine c k for all k

, ? In practice, local search algorithms may be initialised from a feasible solution chosen at random. The choice of local improvements could also be random whenever several candidates are available. What can still be said about the efficiency of local search? Are there instances were not only some but most possible search paths end at a solution whose value is far from the optimum?

P. Assouad, Densité et dimension'. French, Annales de l'institut Fourier, vol.33, pp.233-282, 1983.

C. Berge, Hypergraphes: combinatoire des ensembles finis. French. GauthierVillars, 1987.

. Scoot-aaronson, The Scientific Case for P = NP, p.19, 2014.

A. Abdelkader and D. M. Mount, Economical Delone Sets for Approximating Convex Bodies, 16th Scandinavian Symposium and Workshops on Algorithm Theory, vol.101, p.102, 2018.

K. Pankaj, N. H. Agarwal, and . Mustafa, Independent set of intersection graphs of convex objects in 2D, Computational Geometry, vol.34, issue.2, p.30, 2006.

K. Pankaj, J. Agarwal, M. Pach, and . Sharir, State of the Union (of Geometric Objects): A Review, Computational Geometry: Twenty Years Later, vol.42, p.23, 2008.

K. Pankaj, J. Agarwal, and . Pan, Near-Linear Algorithms for Geometric Hitting Sets and Set Covers, Proceedings of the Thirtieth Annual Symposium on Computational Geometry, vol.271, p.28, 2014.

. Noga-alon, A Non-linear Lower Bound for Planar Epsilon-nets, Discrete & Computational Geometry, vol.47, p.22, 2012.

N. Alon, P. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, vol.3, issue.4, p.82, 1990.

D. Antunes, C. Mathieu, and N. H. Mustafa, Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs, 25th Annual European Symposium on Algorithms, vol.87, pp.1-8, 2017.

B. Aronov, E. Mark-de-berg, M. Ezra, and . Sharir, Improved Bounds for the Union of Locally Fat Objects in the Plane, SIAM Journal on Computing, vol.43, p.67, 2014.

B. Aronov, E. Ezra, and M. Sharir, Small-Size -Nets for AxisParallel Rectangles and Boxes, SIAM Journal on Computing, vol.39, p.67, 2010.

S. Arya, D. Guilherme, D. M. Da-fonseca, and . Mount, On the Combinatorial Complexity of Approximating Polytopes, Discrete & Computational Geometry, vol.58, pp.849-870, 2017.

S. Arya, D. Guilherme, D. M. Da-fonseca, and . Mount, Optimal Approximate Polytope Membership, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, p.102

S. Arya, D. Guilherme, D. M. Da-fonseca, and . Mount, Optimal AreaSensitive Bounds for Polytope Approximation, Proceedings of the 28th Annual ACM Symposium on Computational Geometry, p.68, 2012.

V. Arya, N. Garg, R. Khandekar, and A. Meyerson, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, vol.33, p.80, 2004.

R. Aschner, M. J. Katz, G. Morgenstern, and Y. Yuditsky, Approximation Schemes for Covering and Packing, WALCOM: Algorithms and Computation: 7th International Workshop. Proceedings. 2013, pp.89-100

I. Bárány, Random polytopes, convex bodies, and approximation'. In: Stochastic Geometry, p.59, 2007.

I. Bárány and D. G. Larman, Convex bodies, economic cap coverings, random polytopes, Mathematika, vol.35, p.59, 1988.

S. Basu, R. Pollack, and M. Roy, Algorithms in Real Algebraic Geometry, p.60, 2003.

C. Bazgan, Schémas d'approximation et complexité paramétrée'. French. Unobtainable online. Mémoire de DEA, vol.73, p.29, 1995.

S. Ben, -. David, and M. Lindenbaum, Localization vs. Identification of Semi-Algebraic Sets, Machine Learning, vol.32, p.43, 1998.

C. Berge, Hypergraphes: combinatoire des ensembles finis. French. GauthierVillars, 1987.

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp.273-282, 1986.

H. Brönnimann, B. Chazelle, and J. Pach, How hard is halfspace range searching?, In: Discrete & Computational Geometry, vol.10, pp.143-155, 1993.

H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension', Discrete & Computational Geometry, vol.14, pp.463-479, 1995.

N. Bus, S. Garg, H. Nabil, S. Mustafa, and . Ray, Limits of Local Search: Quality and Efficiency, Discrete & Computational Geometry, vol.57, issue.3, pp.607-624, 2017.

N. Bus, S. Garg, H. Nabil, S. Mustafa, and . Ray, Tighter estimates for -nets for disks, Computational Geometry, vol.53, p.28, 2016.

S. Buzaglo, R. Pinchasi, and G. Rote, Topological Hypergraphs'. In: Thirty Essays on Geometric Graph Theory, p.67, 2013.

S. Cabello and D. Gajser, Simple PTAS's for families of graphs excluding a minor, Discrete Applied Mathematics, vol.189, pp.41-48, 2015.

M. Cesati and L. Trevisan, On the efficiency of polynomial time approximation schemes, Information Processing Letters, vol.64, p.73, 1997.

T. M. Chan, Improved Deterministic Algorithms for Linear Programming in Low Dimensions, Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, p.20, 2016.

T. M. Chan and E. Grant, Exact algorithms and APX-hardness results for geometric packing and covering problems, Special Issue: 23rd Canadian Conference on Computational Geometry (CCCG11), vol.47, pp.112-124, 2014.

T. M. Chan, E. Grant, J. Könemann, and M. Sharpe, Weighted Capacitated, Priority, and Geometric Set Cover via Improved QuasiUniform Sampling, Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pp.1576-1585, 2012.

T. M. Chan and S. Har-peled, Approximation Algorithms for Maximum Independent Set of Pseudo-Disks, Discrete & Computational Geometry, vol.48, pp.373-392, 2012.

B. Chazelle, A Note on Haussler's Packing Lemma'. See Section 5.3 from Geometric Discrepancy: An Illustrated Guide by J. Matou?ek. 1992 (cit, vol.50, p.49

B. Chazelle, The Discrepancy Method: Randomness and Complexity, p.45, 2000.

N. Brent, C. J. Clark, D. S. Colbourn, and . Johnson, Unit disk graphs, Discrete Mathematics, vol.86, p.81, 1990.

K. L. Clarkson, A Randomized Algorithm for Closest-Point Queries, SIAM Journal on Computing, vol.17, p.45, 1988.

K. L. Clarkson, New Applications of Random Sampling in Computational Geometry, Discrete & Computational Geometry, vol.2, p.45, 1987.

L. Kenneth, K. Clarkson, and . Varadarajan, Improved Approximation Algorithms for Geometric Set Cover, Discrete & Computational Geometry, vol.37, issue.1, p.23, 2007.

J. Conway, J. A. Neil, and . Sloane, Sphere Packings, Lattices and Groups. Grundlehren der mathematischen Wissenschaften, p.90, 1999.

I. Dinur and D. Steurer, Analytical Approach to Parallel Repetition, Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, p.28, 2014.

R. Downey, A Parameterized Complexity Tutorial, Language and Automata Theory and Applications, LATA. 2012, p.71

K. Dutta, E. Ezra, and A. Ghosh, Two Proofs for Shallow Packings, Discrete & Computational Geometry, vol.56, pp.49-51, 2016.

K. Dutta, A. Ghosh, B. Jartoux, and N. H. Mustafa, Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning, 33rd International Symposium on Computational Geometry, vol.77, p.15, 2017.

A. Ene, S. Har-peled, and B. Raichel, Geometric packing under non-uniform constraints, Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, pp.11-20, 2012.

E. Ezra, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, SIAM Journal on Computing, vol.45, pp.84-101, 2016.

E. Ezra, B. Aronov, and M. Sharir, Improved Bound for the Union of Fat Triangles, Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, SODA, p.67, 2011.

J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, A SemiAlgebraic Version of Zarankiewicz's Problem, Journal of the European Mathematical Society, vol.19, pp.1785-1810, 2017.

G. N. Frederickson, Fast Algorithms for Shortest Paths in Planar Graphs, with Applications'. In: SIAM J. Comput, vol.16, issue.6, p.32, 1987.

M. Gibson, G. Kanade, E. Krohn, and K. R. Varadarajan, An Approximation Scheme for Terrain Guarding, 12th International Workshop, APPROX 2009, and 13th International Workshop, pp.140-148, 2009.

M. Gibson and I. A. Pirwani, Algorithms for Dominating Set in Disk Graphs: Breaking the log n Barrier, Proceedings of the 18th Annual European Symposium on Algorithms (ESA). 2010, pp.243-254

S. Govindarajan, R. Raman, S. Ray, and A. Roy, Packing and Covering with Non-piercing regions, Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), vol.57, pp.1-47, 2016.

L. Guth, H. Nets, and . Katz, On the Erd?s distinct distances problem in the plane, Annals of Mathematics, vol.181, pp.155-190, 2015.

P. Hall, On Representatives of Subsets, Journal of the London Mathematical Society, p.100, 1935.

S. Har-peled, A Simple Proof of the Existence of a Planar Separator, p.101, 2011.

S. Har, -. Peled, and K. Quanrud, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pp.717-728, 2015.

S. Har, -. Peled, and K. Quanrud, Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, p.82, 2016.

D. Haussler, Sphere Packing Numbers for Subsets of the Boolean n-Cube with Bounded Vapnik-Chervonenkis Dimension, Journal of Combinatorial Theory, Series A, vol.69, issue.2, pp.47-51, 1995.

D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete & Computational Geometry, vol.2, pp.127-151, 1987.

M. Hellmuth, L. Ostermeier, and P. F. Stadler, A Survey on Hypergraph Products, Mathematics in Computer Science, vol.6, issue.1, p.46, 2012.

D. S. Hochbaum and W. Maass, Fast approximation algorithms for a nonconvex covering problem, Journal of Algorithms, vol.8, pp.305-323, 1987.

T. Jansen, Introduction to the theory of complexity and approximation algorithms, Lectures on Proof Verification and Approximation Algorithms, p.71, 1998.

B. Jartoux, H. Nabil, and . Mustafa, Optimality of Geometric Local Search, 34th International Symposium on Computational Geometry, 2018.

R. M. Karp, Reducibility among Combinatorial Problems, Complexity of Computer Computations. Springer US, p.28, 1972.

K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, vol.1, issue.1, p.42, 1986.

P. Koebe, .. Der-konformen-abbildung, and &. German, Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, vol.88, p.100, 1936.

J. Komlós, J. Pach, and G. Woeginger, Almost Tight Bounds for -nets, Discrete & Computational Geometry, vol.7, p.22, 1992.

A. Kupavskii, H. Nabil, J. Mustafa, and . Pach, Near-Optimal Lower Bounds for -nets for Half-spaces and Low Complexity Set Systems, A Journey Through Discrete Mathematics: A Tribute to Ji?í Matou?ek, 2017.

A. Kupavskii and N. Zhivotovskiy, When are epsilon-nets small, p.20, 2017.

Y. Li, P. M. Long, and A. Srinivasan, Improved Bounds on the Sample Complexity of Learning, Journal of Computer and System Sciences, vol.62, issue.3, p.49, 2001.

J. Richard, R. E. Lipton, and . Tarjan, A Separator Theorem for Planar Graphs, SIAM Journal on Applied Mathematics, vol.36, issue.2, p.31, 1979.

H. Lynn, H. Loomis, and . Whitney, An inequality related to the isoperimetric inequality, Bulletin of the American Mathematical Society, vol.55, p.100, 1949.

A. M. Macbeath, A Theorem on Non-Homogeneous Lattices, Annals of Mathematics, vol.56, pp.269-293, 1952.

D. Marx, Efficient Approximation Schemes for Geometric Problems?, ' In: Algorithms -ESA 2005: 13th Annual European Symposium, vol.83, p.76, 2005.

D. Marx, Parameterized Complexity of Independence and Domination on Geometric Graphs, Parameterized and Exact Computation: Second International Workshop, vol.83, p.76, 2006.

J. Matou?ek, Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics 18, vol.45, pp.47-49, 1999.

J. Matou?ek, Lectures in Discrete Geometry, vol.68, p.45, 2002.

J. Matou?ek, Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in Combinatorics and Geometry, p.46, 2003.

J. Matou?ek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, vol.23, p.61, 1994.

J. Matou?ek and Z. Patáková, Multilevel Polynomial Partitions and Simplified Range Searching, Discrete & Computational Geometry, vol.54, pp.22-41, 2015.

E. W. Mayr, Lectures on Proof Verification and Approximation Algorithms, vol.1367, p.71, 1998.

G. L. Miller, . Shang-hua, W. Teng, S. A. Thurston, and . Vavasis, Separators for Sphere-packings and Nearest Neighbor Graphs, Journal of the ACM, vol.44, issue.1, p.90, 1997.

H. Nabil and . Mustafa, A Simple Proof of the Shallow Packing Lemma, Discrete & Computational Geometry, vol.55, pp.49-51, 2016.

H. Nabil, K. Mustafa, A. Dutta, and . Ghosh, A Simple Proof of Optimal Epsilon-nets, Combinatorica, p.45, 2017.

H. Nabil, S. Mustafa, and . Ray, Mnets: Hitting Geometric Set Systems with Subsets, Discrete & Computational Geometry, vol.57, pp.625-640, 2017.

H. Nabil, S. Mustafa, and . Ray, Improved Results on Geometric Hitting Set Problems, Discrete & Computational Geometry, vol.44, pp.30-32, 2010.

H. Nabil, K. R. Mustafa, and . Varadarajan, Epsilon-approximations and Epsilon-nets, Handbook of Discrete and Computational Geometry, p.45, 2017.

J. Ne?et?il and P. Mendez, Sparsity. Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol.28, p.95, 2012.

J. Pach and P. K. Agarwal, Combinatorial Geometry, p.45, 1995.

J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, Journal of the American Mathematical Society, vol.26, p.23, 2013.

N. Rubin, An Improved Bound for Weak Epsilon-Nets in the Plane, p.45, 2018.

N. Sauer, On the Density of Families of Sets, Journal of Combinatorial Theory, Series A, vol.13, issue.1, p.39, 1972.

M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete & Computational Geometry, vol.6, p.42, 1991.

S. Shelah, A Combinatorial Problem, Stability and Order for Models and Theories in Infinitary Languages, Pacific Journal of Mathematics, vol.41, p.39, 1972.

P. Turán, ;. Hungarian, and G. , Egy gráfelméleti széls?érték feladatról, In: Matematikai és Fizikai Lapok, vol.48, p.101, 1941.

N. Vladimir, A. Vapnik, . Ya, and . Chervonenkis, Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data, Trans. of '?????? ??????????? ?????????? ?????? ????????? ??????? ? ?? ???????????? ? ?????? ?????? ???????????? ??????? ?? ???????????? ??????'. Russian. In: ??????-???? ? ????????????, vol.2, pp.42-53, 1971.

R. Kasturi and . Varadarajan, Epsilon Nets and Union Complexity, Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, p.23, 2009.

R. Kasturi and . Varadarajan, Weighted Geometric Set Cover via Quasi-Uniform Sampling, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC. 2010, pp.641-648