{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T11:31:58Z","timestamp":1768735918760,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00454-019-00075-0","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T16:05:35Z","timestamp":1552665935000},"page":"756-777","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning"],"prefix":"10.1007","volume":"61","author":[{"given":"Kunal","family":"Dutta","sequence":"first","affiliation":[]},{"given":"Arijit","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Jartoux","sequence":"additional","affiliation":[]},{"given":"Nabil H.","family":"Mustafa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"issue":"2","key":"75_CR1","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"75_CR2","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \n                    \n                      \n                    \n                    $$\\epsilon $$\n                    \n                      \n                        \u03f5\n                      \n                    \n                  -nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"75_CR3","doi-asserted-by":"crossref","unstructured":"Arya, S., da\u00a0Fonseca, G.D., Mount, D.M.: Optimal area-sensitive bounds for polytope approximation. In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG\u201912), pp. 363\u2013372. ACM, New York (2012)","DOI":"10.1145\/2261250.2261305"},{"key":"75_CR4","unstructured":"Arya, S., da\u00a0Fonseca, G.D., Mount, D.M.: On the combinatorial complexity of approximating polytopes. In: Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916). LIPIcs. Leibniz International Proceedings in Informatics, vol. 51, pp. 11:1\u201311:15. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2016)"},{"key":"75_CR5","first-page":"77","volume-title":"Stochastic Geometry. Lecture Notes in Mathematics","author":"I B\u00e1r\u00e1ny","year":"2007","unstructured":"B\u00e1r\u00e1ny, I.: Random polytopes, convex bodies, and approximation. In: Weil, W. (ed.) Stochastic Geometry. Lecture Notes in Mathematics, vol. 1892, pp. 77\u2013118. Springer, Berlin (2007)"},{"key":"75_CR6","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1112\/S0025579300015266","volume":"35","author":"I B\u00e1r\u00e1ny","year":"1988","unstructured":"B\u00e1r\u00e1ny, I., Larman, D.G.: Convex bodies, economic cap coverings, random polytopes. Mathematika 35, 274\u2013291 (1988)","journal-title":"Mathematika"},{"key":"75_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05355-3","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"S Basu","year":"2003","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2003)"},{"key":"75_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-1-4614-0110-0_6","volume-title":"Thirty Essays on Geometric Graph Theory","author":"S Buzaglo","year":"2013","unstructured":"Buzaglo, S., Pinchasi, R., Rote, G.: Topological hypergraphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 71\u201381. Springer, New York (2013)"},{"key":"75_CR9","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912), pp. 1576\u20131585. ACM, New York (2012)","DOI":"10.1137\/1.9781611973099.125"},{"key":"75_CR10","unstructured":"Chazelle, B.: A note on Haussler\u2019s Packing Lemma (1992). See Section 5.3 from Geometric Discrepancy: An Illustrated Guide by J. Matou\u0161ek"},{"issue":"1","key":"75_CR11","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms 9(1), 9:1\u20139:17 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"75_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"75_CR13","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1007\/s00454-016-9824-0","volume":"56","author":"K Dutta","year":"2016","unstructured":"Dutta, K., Ezra, E., Ghosh, A.: Two proofs for shallow packings. Discrete Comput. Geom. 56(4), 910\u2013939 (2016)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"75_CR14","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/140977746","volume":"45","author":"E Ezra","year":"2016","unstructured":"Ezra, E.: A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension. SIAM J. Comput. 45(1), 84\u2013101 (2016)","journal-title":"SIAM J. Comput."},{"key":"75_CR15","doi-asserted-by":"crossref","unstructured":"Ezra, E., Aronov, B., Sharir, S.: Improved bound for the union of fat triangles. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911), pp. 1778\u20131785. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.136"},{"issue":"6","key":"75_CR16","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4171\/JEMS\/705","volume":"19","author":"J Fox","year":"2017","unstructured":"Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz\u2019s problem. J. Eur. Math. Soc. (JEMS) 19(6), 1785\u20131810 (2017)","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"issue":"1","key":"75_CR17","doi-asserted-by":"publisher","first-page":"155","DOI":"10.4007\/annals.2015.181.1.2","volume":"181","author":"L Guth","year":"2015","unstructured":"Guth, L., Katz, N.H.: On the Erd\u00f6s distinct distances problem in the plane. Ann. Math. 181(1), 155\u2013190 (2015)","journal-title":"Ann. Math."},{"issue":"2","key":"75_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0097-3165(95)90052-7","volume":"69","author":"D Haussler","year":"1995","unstructured":"Haussler, D.: Sphere packing numbers for subsets of the Boolean \n                    \n                      \n                    \n                    $$n$$\n                    \n                      \n                        n\n                      \n                    \n                  -cube with bounded Vapnik-Chervonenkis dimension. J. Combin. Theory Ser. A 69(2), 217\u2013232 (1995)","journal-title":"J. Combin. Theory Ser. A"},{"key":"75_CR19","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-3-319-44479-6_21","volume-title":"A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek","author":"A Kupavskii","year":"2017","unstructured":"Kupavskii, A., Mustafa, N.H., Pach, J.: Near-optimal lower bounds for \n                    \n                      \n                    \n                    $$\\epsilon $$\n                    \n                      \n                        \u03f5\n                      \n                    \n                  -nets for half-spaces and low complexity set systems. In: Loebl, M., Ne\u0161et\u0159il, J., Thomas, R. (eds.) A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 527\u2013541. Springer, Cham (2017)"},{"issue":"3","key":"75_CR20","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y Li","year":"2001","unstructured":"Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the sample complexity of learning. J. Comput. System Sci. 62(3), 516\u2013527 (2001)","journal-title":"J. Comput. System Sci."},{"key":"75_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3","volume-title":"Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics","author":"J Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics, vol. 18. Springer, Berlin (1999)"},{"key":"75_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)"},{"issue":"1","key":"75_CR23","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00454-015-9701-2","volume":"54","author":"J Matou\u0161ek","year":"2015","unstructured":"Matou\u0161ek, J., Pat\u00e1kov\u00e1, Z.: Multilevel polynomial partitions and simplified range searching. Discrete Comput. Geom. 54(1), 22\u201341 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"75_CR24","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1137\/S009753979018330X","volume":"23","author":"J Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J., Pach, J., Sharir, M., Sifrony, S., Welzl, E.: Fat triangles determine linearly many holes. SIAM J. Comput. 23(1), 154\u2013169 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"75_CR25","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00454-016-9767-5","volume":"55","author":"NH Mustafa","year":"2016","unstructured":"Mustafa, N.H.: A simple proof of the shallow packing lemma. Discrete Comput. Geom. 55(3), 739\u2013743 (2016)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"75_CR26","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/s00454-016-9845-8","volume":"57","author":"NH Mustafa","year":"2017","unstructured":"Mustafa, N.H., Ray, S.: \n                    \n                      \n                    \n                    $$\\epsilon $$\n                    \n                      \n                        \u03f5\n                      \n                    \n                  -Mnets: hitting geometric set systems with subsets. Discrete Comput. Geom. 57(3), 625\u2013640 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"75_CR27","volume-title":"Handbook of Discrete and Computational Geometry","author":"NH Mustafa","year":"2017","unstructured":"Mustafa, N.H., Varadarajan, K.: Epsilon-approximations and epsilon-nets. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (2017)"},{"key":"75_CR28","volume-title":"Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"J Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1995)"},{"issue":"1","key":"75_CR29","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Combin. Theory Ser. A 13(1), 145\u2013147 (1972)","journal-title":"J. Combin. Theory Ser. A"},{"key":"75_CR30","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem, stability and order for models and theories in infinitary languages. Pacific J. Math. 41, 247\u2013261 (1972)","journal-title":"Pacific J. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00075-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00075-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00075-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:08:14Z","timestamp":1584144494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00075-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["75"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00075-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,15]]},"assertion":[{"value":"27 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}