Sampling in Combinatorial and Geometric Set Systems

Mustafa, Nabil

doi:10.1090/surv/265

AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Sampling in Combinatorial and Geometric Set Systems

About this Title

Nabil H. Mustafa, Université Sorbonne Paris Nord, Villetaneuse, France

Publication: Mathematical Surveys and Monographs
Publication Year: 2022; Volume 265
ISBNs: 978-1-4704-6156-0 (print); 978-1-4704-6873-6 (online)
DOI: https://doi.org/10.1090/surv/265

PDF View full volume as PDF

Read more about this volume

Boris Aronov, Esther Ezra, and Micha Sharir, Small-size $\epsilon$-nets for axis-parallel rectangles and boxes, SIAM J. Comput. 39 (2010), no. 7, 3248–3282. MR 2678074, DOI 10.1137/090762968
Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan, Geometric approximation via coresets, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 1–30. MR 2178310, DOI 10.4171/PRIMS/172
Pankaj K. Agarwal, János Pach, and Micha Sharir, State of the union (of geometric objects), Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 9–48. MR 2405676, DOI 10.1090/conm/453/08794
Pankaj K. Agarwal and Micha Sharir, Arrangements and their applications, Handbook of computational geometry, North-Holland, Amsterdam, 2000, pp. 49–119. MR 1746675, DOI 10.1016/B978-044482537-7/50003-6
Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Maria Axenovich and Torsten Ueckerdt, Density of range capturing hypergraphs, J. Comput. Geom. 7 (2016), no. 1, 1–21. MR 3455619, DOI 10.20382/jocg.v7i1a1
Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 575–598. MR 1730187
R. Alexander, Geometric methods in the study of irregularities of distribution, Combinatorica 10 (1990), no. 2, 115–136. MR 1082645, DOI 10.1007/BF02123006
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, and Shakhar Smorodinsky, Weak $\epsilon$-nets and interval chains, J. ACM 55 (2008), no. 6, Art. 28, 32. MR 2477488, DOI 10.1145/1455248.1455252
Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman, Point selections and weak $\epsilon$-nets for convex hulls, Combin. Probab. Comput. 1 (1992), no. 3, 189–200. MR 1208800, DOI 10.1017/S0963548300000225
Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir, Improved bounds for the union of locally fat objects in the plane, SIAM J. Comput. 43 (2014), no. 2, 543–572. MR 3188401, DOI 10.1137/120891241
Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount, Optimal bound on the combinatorial complexity of approximating polytopes, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2020, pp. 786–805. MR 4141230
József Beck and William W. L. Chen, Irregularities of distribution, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR 903025, DOI 10.1017/CBO9780511565984
Hervé Brönnimann, Bernard Chazelle, and Jiří Matoušek, Product range spaces, sensitive sampling, and derandomization, SIAM J. Comput. 28 (1999), no. 5, 1552–1575. MR 1694192, DOI 10.1137/S0097539796260321
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities, Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence; With a foreword by Michel Ledoux. MR 3185193, DOI 10.1093/acprof:oso/9780199535255.001.0001
Boris Bukh, Jiří Matoušek, and Gabriel Nivasch, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math. 182 (2011), 199–208. MR 2783971, DOI 10.1007/s11856-011-0029-1
Sarit Buzaglo, Rom Pinchasi, and Günter Rote, Topological hypergraphs, Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 71–81. MR 3205150, DOI 10.1007/978-1-4614-0110-0_{6}
József Balogh and Wojciech Samotij, An efficient container lemma, Discrete Anal. , posted on (2020), Paper No. 17, 56. MR 4186910, DOI 10.19086/da
Mark de Berg and Otfried Schwarzkopf, Cuttings and applications, Internat. J. Comput. Geom. Appl. 5 (1995), no. 4, 343–355. MR 1359425, DOI 10.1142/S0218195995000210
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, J. Assoc. Comput. Mach. 36 (1989), no. 4, 929–965. MR 1072253, DOI 10.1145/76359.76371
J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom. 19 (1998), no. 4, 485–519. MR 1620060, DOI 10.1007/PL00009366
Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986. Set systems, hypergraphs, families of vectors and combinatorial probability. MR 866142
Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray, Tighter estimates for $ϵ$-nets for disks, Comput. Geom. 53 (2016), 27–35. MR 3454542, DOI 10.1016/j.comgeo.2015.12.002
B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), no. 3, 229–249. MR 1092541, DOI 10.1007/BF02122778
Victor Chepoi, Kolja Knauer, and Manon Philibert, Two-dimensional partial cubes, Electron. J. Combin. 27 (2020), no. 3, Paper No. 3.29, 40. MR 4245142, DOI 10.37236/8934
M. Csikós and N. H. Mustafa. Optimal approximations made easy. CoRR abs/2008.08970, 2021. arXiv:2008.08970. url: https://arxiv.org/abs/2008.08970.
Bernard Chazelle and Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms 21 (1996), no. 3, 579–597. MR 1417665, DOI 10.1006/jagm.1996.0060
Mónika Csikós, Nabil H. Mustafa, and Andrey Kupavskii, Tight lower bounds on the VC-dimension of geometric set systems, J. Mach. Learn. Res. 20 (2019), Paper No. 81, 8. MR 3960935
Kenneth L. Clarkson and Peter W. Shor, Applications of random sampling in computational geometry. II, Discrete Comput. Geom. 4 (1989), no. 5, 387–421. MR 1014736, DOI 10.1007/BF02187740
N. Srivastava, Discrepancy, graphs, and the Kadison-Singer problem, Asia Pac. Math. Newsl. 3 (2013), no. 4, 15–20. MR 3156130
Kenneth L. Clarkson and Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom. 37 (2007), no. 1, 43–58. MR 2279863, DOI 10.1007/s00454-006-1273-8
Bernard Chazelle and Emo Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete Comput. Geom. 4 (1989), no. 5, 467–489. MR 1014739, DOI 10.1007/BF02187743
Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2012, pp. 1576–1585. MR 3205315
B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, Improved bounds on weak $\epsilon$-nets for convex sets, Discrete Comput. Geom. 13 (1995), no. 1, 1–15. MR 1300506, DOI 10.1007/BF02574025
Bernard Chazelle, The discrepancy method, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR 1779341, DOI 10.1017/CBO9780511626371
Timothy M. Chan, Optimal partition trees, Discrete Comput. Geom. 47 (2012), no. 4, 661–690. MR 2901245, DOI 10.1007/s00454-012-9410-z
Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom. 9 (1993), no. 2, 145–158. MR 1194032, DOI 10.1007/BF02189314
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), no. 2, 99–160. MR 1032370, DOI 10.1007/BF02187783
Kenneth L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom. 2 (1987), no. 2, 195–222. MR 884226, DOI 10.1007/BF02187879
Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM J. Comput. 17 (1988), no. 4, 830–847. MR 953296, DOI 10.1137/0217052
M. Csikós. Personal communication. 2016.
Kunal Dutta, Esther Ezra, and Arijit Ghosh, Two proofs for shallow packings, Discrete Comput. Geom. 56 (2016), no. 4, 910–939. MR 3561795, DOI 10.1007/s00454-016-9824-0
L. Devroye, Györfi and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.
Devdatt P. Dubhashi and Alessandro Panconesi, Concentration of measure for the analysis of randomized algorithms, Cambridge University Press, Cambridge, 2009. MR 2547432, DOI 10.1017/CBO9780511581274
M. Dyer, B. Gärtner, N. Megiddo and E. Welzl. Linear programming. Handbook of Discrete and Computational Geometry. CRC Press, 2018. pp. 1291–1310.
David Eisenstat and Dana Angluin, The VC dimension of $k$-fold union, Inform. Process. Lett. 101 (2007), no. 5, 181–184. MR 2291190, DOI 10.1016/j.ipl.2006.10.004
Guy Even, Dror Rawitz, and Shimon Shahar, Hitting sets when the VC-dimension is small, Inform. Process. Lett. 95 (2005), no. 2, 358–362. MR 2149262, DOI 10.1016/j.ipl.2005.03.010
David Eisenstat, $k$-fold unions of low-dimensional concept classes, Inform. Process. Lett. 109 (2009), no. 23-24, 1232–1234. MR 2571754, DOI 10.1016/j.ipl.2009.09.005
Esther Ezra, Sariel Har-Peled, Haim Kaplan, and Micha Sharir, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, Discrete Comput. Geom. 64 (2020), no. 1, 109–173. MR 4110531, DOI 10.1007/s00454-019-00141-7
Esther Ezra, A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension, SIAM J. Comput. 45 (2016), no. 1, 84–101. MR 3452262, DOI 10.1137/140977746
Alan Frieze and MichałKaroński, Introduction to random graphs, Cambridge University Press, Cambridge, 2016. MR 3675279, DOI 10.1017/CBO9781316339831
Dan Feldman and Michael Langberg, A unified framework for approximating and clustering data, STOC’11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 569–578. MR 2932007, DOI 10.1145/1993636.1993712
Jacob Fox and János Pach, Separator theorems and Turán-type results for planar intersection graphs, Adv. Math. 219 (2008), no. 3, 1070–1080. MR 2442062, DOI 10.1016/j.aim.2008.06.002
Peter Frankl and János Pach, On the number of sets in a null $t$-design, European J. Combin. 4 (1983), no. 1, 21–23. MR 694464, DOI 10.1016/S0195-6698(83)80004-3
Zoltán Füredi and Miklós Simonovits, The history of degenerate (bipartite) extremal graph problems, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264. MR 3203598, DOI 10.1007/978-3-642-39286-3_{7}
Peter Frankl, The shifting technique in extremal set theory, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 81–110. MR 905277
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
B. Gärtner, J. Matoušek, L. Rüst, and P. Škovroň, Violator spaces: structure and algorithms, Discrete Appl. Math. 156 (2008), no. 11, 2124–2141. MR 2437006, DOI 10.1016/j.dam.2007.08.048
D. Haussler, N. Littlestone, and M. K. Warmuth, Predicting $\{0,1\}$-functions on randomly drawn points, Inform. and Comput. 115 (1994), no. 2, 248–292. MR 1304811, DOI 10.1006/inco.1994.1097
Sariel Har-Peled, Geometric approximation algorithms, Mathematical Surveys and Monographs, vol. 173, American Mathematical Society, Providence, RI, 2011. MR 2760023, DOI 10.1090/surv/173
Sariel Har-Peled and Micha Sharir, Relative $(p,\epsilon )$-approximations in geometry, Discrete Comput. Geom. 45 (2011), no. 3, 462–496. MR 2770547, DOI 10.1007/s00454-010-9248-1
Lingxiao Huang and Nisheeth K. Vishnoi, Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal, STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2020] ©2020, pp. 1416–1429. MR 4141850
David Haussler and Emo Welzl, $\epsilon$-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127–151. MR 884223, DOI 10.1007/BF02187876
David Haussler, Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A 69 (1995), no. 2, 217–232. MR 1313896, DOI 10.1016/0097-3165(95)90052-7
Russell Impagliazzo and Valentine Kabanets, Constructive proofs of concentration bounds, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 6302, Springer, Berlin, 2010, pp. 617–631. MR 2755867, DOI 10.1007/978-3-642-15369-3_{4}6
Andrey Kupavskii, Nabil H. Mustafa, and János Pach, New lower bounds for $\epsilon$-nets, 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 51, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 54, 16. MR 3540896
Andrey Kupavskii, Nabil H. Mustafa, and János Pach, Near-optimal lower bounds for $\epsilon$-nets for half-spaces and low complexity set systems, A journey through discrete mathematics, Springer, Cham, 2017, pp. 527–541. MR 3726612
János Komlós, János Pach, and Gerhard Woeginger, Almost tight bounds for $\epsilon$-nets, Discrete Comput. Geom. 7 (1992), no. 2, 163–173. MR 1139078, DOI 10.1007/BF02187833
Philip Klein and Neal E. Young, On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms, SIAM J. Comput. 44 (2015), no. 4, 1154–1172. MR 3390154, DOI 10.1137/12087222X
Yi Li, Philip M. Long, and Aravind Srinivasan, Improved bounds on the sample complexity of learning, J. Comput. System Sci. 62 (2001), no. 3, 516–527. MR 1824457, DOI 10.1006/jcss.2000.1741
Jesús A. De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil H. Mustafa, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Bull. Amer. Math. Soc. (N.S.) 56 (2019), no. 3, 415–511. MR 3974609, DOI 10.1090/bull/1653
Philip M. Long, Using the pseudo-dimension to analyze approximation algorithms for integer programming, Algorithms and data structures (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2125, Springer, Berlin, 2001, pp. 26–37. MR 1936398, DOI 10.1007/3-540-44634-6_{4}
Nabil H. Mustafa, Kunal Dutta, and Arijit Ghosh, A simple proof of optimal epsilon nets, Combinatorica 38 (2018), no. 5, 1269–1277. MR 3884789, DOI 10.1007/s00493-017-3564-5
J. Matoušek and B. Gärtner. Understanding and Using Linear Programming. Springer, 2007.
Nabil H. Mustafa and János Pach, On the Zarankiewicz problem for intersection hypergraphs, J. Combin. Theory Ser. A 141 (2016), 1–7. MR 3479234, DOI 10.1016/j.jcta.2016.02.001
Michael Matheny and Jeff M. Phillips, Practical low-dimensional halfspace range space sampling, 26th European Symposium on Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 112, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 62, 14. MR 3847688
Nabil H. Mustafa and Saurabh Ray, An optimal extension of the centerpoint theorem, Comput. Geom. 42 (2009), no. 6-7, 505–510. MR 2519371, DOI 10.1016/j.comgeo.2007.10.004
Nabil H. Mustafa and Saurabh Ray, $\varepsilon$-Mnets: hitting geometric set systems with subsets, Discrete Comput. Geom. 57 (2017), no. 3, 625–640. MR 3614776, DOI 10.1007/s00454-016-9845-8
Jiří Matoušek and Uli Wagner, New constructions of weak $\epsilon$-nets, Discrete Comput. Geom. 32 (2004), no. 2, 195–206. MR 2074337, DOI 10.1007/s00454-004-1116-4
Jiří Matoušek, Emo Welzl, and Lorenz Wernisch, Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993), no. 4, 455–466. MR 1262921, DOI 10.1007/BF01303517
J. Matoušek. Lectures in Discrete Geometry. Springer, 2002.
Jiří Matoušek, Cutting hyperplane arrangements, Discrete Comput. Geom. 6 (1991), no. 5, 385–406. MR 1115098, DOI 10.1007/BF02574697
Jiří Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), no. 3, 315–334. ACM Symposium on Computational Geometry (North Conway, NH, 1991). MR 1174360, DOI 10.1007/BF02293051
Jiří Matoušek, Reporting points in halfspaces, Comput. Geom. 2 (1992), no. 3, 169–186. MR 1190599, DOI 10.1016/0925-7721(92)90006-E
J. Matoušek, Tight upper bounds for the discrepancy of half-spaces, Discrete Comput. Geom. 13 (1995), no. 3-4, 593–601. MR 1318799, DOI 10.1007/BF02574066
Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, J. Comput. System Sci. 50 (1995), no. 2, 203–208. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991). MR 1330253, DOI 10.1006/jcss.1995.1018
J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Springer, 1999.
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
Wolfgang Mulzer, Five proofs of Chernoff’s bound with applications, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 124 (2018), 59–76. MR 3793013
Nabil H. Mustafa, A simple proof of the shallow packing lemma, Discrete Comput. Geom. 55 (2016), no. 3, 739–743. MR 3473678, DOI 10.1007/s00454-016-9767-5
Nabil H. Mustafa, Computing optimal epsilon-nets is as easy as finding an unhit set, 46th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 132, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 87, 12. MR 3984904
Márton Naszódi and Steven Taschuk, On the transversal number and VC-dimension of families of positive homothets of a convex body, Discrete Math. 310 (2010), no. 1, 77–82. MR 2558970, DOI 10.1016/j.disc.2009.07.030
Márton Naszódi, Approximating a convex body by a polytope using the epsilon-net theorem, Discrete Comput. Geom. 61 (2019), no. 3, 686–693. MR 3918553, DOI 10.1007/s00454-018-9977-0
Aleksandar Nikolov, Tighter bounds for the discrepancy of boxes and polytopes, Mathematika 63 (2017), no. 3, 1091–1113. MR 3731316, DOI 10.1112/S0025579317000250
János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145, DOI 10.1002/9781118033203
Evangelia Pyrga and Saurabh Ray, New existence proofs for $\epsilon$-nets, Computational geometry (SCG’08), ACM, New York, 2008, pp. 199–207. MR 2504287, DOI 10.1145/1377676.1377708
János Pach and Gábor Tardos, Tight lower bounds for the size of epsilon-nets, J. Amer. Math. Soc. 26 (2013), no. 3, 645–658. MR 3037784, DOI 10.1090/S0894-0347-2012-00759-0
M. Pellegrini, On counting pairs of intersecting segments and off-line triangle range searching, Algorithmica 17 (1997), no. 4, 380–398. MR 1429210, DOI 10.1007/BF02523679
J. M. Phillips. Coresets and sketches. Handbook of Discrete and Computational Geometry. CRC Press, 2018. pp. 1269–1286.
Natan Rubin, An improved bound for weak epsilon-nets in the plane, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 224–235. MR 3899592, DOI 10.1109/FOCS.2018.00030
Subhash Suri, Csaba D. Tóth, and Yunhong Zhou, Range counting over multidimensional data streams, Discrete Comput. Geom. 36 (2006), no. 4, 633–655. MR 2267550, DOI 10.1007/s00454-006-1269-4
Micha Sharir and Emo Welzl, A combinatorial bound for linear programming and related problems, STACS 92 (Cachan, 1992) Lecture Notes in Comput. Sci., vol. 577, Springer, Berlin, 1992, pp. 569–579. MR 1255620
Micha Sharir, On $k$-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991), no. 6, 593–613. MR 1121331, DOI 10.1007/BF02574706
Michael Z. Spivey, The art of proving binomial identities, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2019. MR 3931743, DOI 10.1201/9781351215824
M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Probab. 22 (1994), no. 1, 28–76. MR 1258865
V. N. Vapnik and A. Ja. Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264–279 (Russian, with English summary). MR 0288823
K. R. Varadarajan and X. Xiao. On the sensitivity of shape fitting problems. Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. pp. 486–497.
Kasturi Varadarajan, Weighted geometric set cover via quasi-uniform sampling, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 641–647. MR 2743313
Uli Wagner, $k$-sets and $k$-facets, Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 443–513. MR 2405692, DOI 10.1090/conm/453/08810

AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Sampling in Combinatorial and Geometric Set Systems

About this Title

Table of Contents

References [Enhancements On Off] (What's this?)