{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:36:01Z","timestamp":1742924161950,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_20","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"281-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Unsplittable Coverings in the Plane"],"prefix":"10.1007","author":[{"given":"J\u00e1nos","family":"Pach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"issue":"2","key":"20_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00454-010-9323-7","volume":"47","author":"N Alon","year":"2012","unstructured":"Alon, N.: A non-linear lower bound for planar epsilon-nets. Discrete Comput. Geom. 47(2), 235\u2013244 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR2","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. Wiley, Hoboken, NJ (2008)","edition":"3"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1007\/s00454-009-9238-3","volume":"44","author":"G Aloupis","year":"2010","unstructured":"Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., Ramos, P.: Decomposition of multiple coverings into more parts. Discrete Comput. Geom. 44(3), 706\u2013723 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-40104-6_7","volume-title":"Algorithms and Data Structures","author":"A Asinowski","year":"2013","unstructured":"Asinowski, A., et al.: Coloring hypergraphs induced by dynamic point sets and bottomless rectangles. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 73\u201384. Springer, Heidelberg (2013)"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/110856332","volume":"27","author":"B Bollob\u00e1s","year":"2013","unstructured":"Bollob\u00e1s, B., Pritchard, D., Rothvo\u00df, T., Scott, A.: Cover-decomposition and polychromatic numbers. SIAM J. Discrete Math. 27(1), 240\u2013256 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR6","unstructured":"Buchsbaum, A.L., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering, the sensor cover problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1056\u20131063 (2007)"},{"issue":"1","key":"20_CR7","first-page":"240","volume":"4","author":"J Cardinal","year":"2013","unstructured":"Cardinal, J., Knauer, K., Micek, P., Ueckerdt, T.: Making triangles colorful. J. Comput. Geom. 4(1), 240\u2013246 (2013)","journal-title":"J. Comput. Geom."},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"1948","DOI":"10.1137\/140955975","volume":"28","author":"J Cardinal","year":"2014","unstructured":"Cardinal, J., Knauer, K., Micek, P., Ueckerdt, T.: Making octants colorful and related covering decomposition problems. SIAM J. Discrete Math. 28(4), 1948\u20131959 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR9","first-page":"5","volume":"11","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P.: On a combinatorial problem. Nordisk Mat. Tidskr. 11, 5\u201310 (1963). 40","journal-title":"Nordisk Mat. Tidskr."},{"key":"20_CR10","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on \n                      \n                        \n                      \n                      $$3$$\n                    -chromatic hypergraphs and some related questions. In: Infinite and finite sets (Colloq., Keszthely 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. II, pp. 609\u2013627. Colloq. Math. Soc. J\u00e1nos Bolyai, 10"},{"key":"20_CR11","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94\u2013136 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"20_CR13","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U Feige","year":"2002","unstructured":"Feige, U., Halld\u00f3rsson, M.M., Kortsarz, G.: Approximating the domatic number. SIAM J. Comput. 32(1), 172\u2013195 (2002)","journal-title":"SIAM J. Comput."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Fejes T\u00f3th, G.: New results in the theory of packing and covering. In: Gruber, P., Wills, J. (eds.) Convexity and Its Applications, pp. 318\u2013359. Birkh\u00e4user, Basel (1983)","DOI":"10.1007\/978-3-0348-5858-8_14"},{"key":"20_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-58043-7_11","volume-title":"New Trends in Discrete and Computational Geometry","author":"G T\u00f3th","year":"1993","unstructured":"T\u00f3th, G., Kuperberg, W.: A survey of recent results in the theory of packing and covering. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 10, pp. 251\u2013279. Springer, Heidelberg (1993)"},{"key":"20_CR16","unstructured":"Fulek, R.: Personal communication (2010). See also in [36]"},{"key":"20_CR17","unstructured":"Fulek, R., Hubai, T., Keszegh, B., Nagy, Z., Rothvo\u00df, T., Vizer, M.: Personal communication (2010)"},{"issue":"5","key":"20_CR18","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00493-012-2679-y","volume":"32","author":"H Gebauer","year":"2012","unstructured":"Gebauer, H., Gebauer, H.: Disproof of the neighborhood conjecture with implications to SAT. Combinatorica 32(5), 573\u2013587 (2012)","journal-title":"Combinatorica"},{"issue":"2","key":"20_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00454-011-9353-9","volume":"46","author":"M Gibson","year":"2011","unstructured":"Gibson, M., Varadarajan, K.: Optimally decomposing coverings with translates of a convex polygon. Discrete Comput. Geom. 46(2), 313\u2013333 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"12","DOI":"10.2307\/2689288","volume":"48","author":"B Gr\u00fcnbaum","year":"1975","unstructured":"Gr\u00fcnbaum, B.: Venn diagrams and independent families of sets. Math. Mag. 48, 12\u201323 (1975)","journal-title":"Math. Mag."},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: \n                      \n                        \n                      \n                      $$\\epsilon $$\n                    -nets and simplex range queries. Discrete Comput. Geom. 2(2), 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/s00454-011-9377-1","volume":"47","author":"B Keszegh","year":"2012","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Octants are cover-decomposable. Discrete Comput. Geom. 47(3), 598\u2013609 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"20_CR23","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/j.comgeo.2013.12.001","volume":"47","author":"B Keszegh","year":"2014","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Octants are cover-decomposable into many coverings. Comput. Geom. 47(5), 585\u2013588 (2014)","journal-title":"Comput. Geom."},{"issue":"4","key":"20_CR24","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s00454-014-9582-9","volume":"51","author":"B Keszegh","year":"2014","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Convex polygons are self-coverable. Discrete Comput. Geom. 51(4), 885\u2013895 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR25","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes. \n                      arXiv:1410.0258"},{"key":"20_CR26","unstructured":"Kov\u00e1cs, I. Indecomposable coverings with homothetic polygons. \n                      arXiv: 1312.4597"},{"key":"20_CR27","unstructured":"Mani-Levitska, P., Pach, J.: Decomposition problems for multiple coverings with unit balls, manuscript (1986). Parts of the manuscript are available at \n                      http:\/\/www.math.nyu.edu\/~pach\/publications\/unsplittable.pdf"},{"issue":"2","key":"20_CR28","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1090\/S0002-9939-2012-11334-6","volume":"141","author":"J Matou\u0161ek","year":"2013","unstructured":"Matou\u0161ek, J.: The determinant bound for discrepancy is almost tight. Proc. Amer. Math. Soc. 141(2), 451\u2013460 (2013)","journal-title":"Proc. Amer. Math. Soc."},{"key":"20_CR29","first-page":"31","volume":"30","author":"EW Miller","year":"1937","unstructured":"Miller, E.W.: On a property of families of sets. C. R. Soc. Sci. Varsovie 30, 31\u201338 (1937)","journal-title":"C. R. Soc. Sci. Varsovie"},{"issue":"1","key":"20_CR30","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.disc.2009.07.030","volume":"310","author":"M Nasz\u00f3di","year":"2010","unstructured":"Nasz\u00f3di, M., Taschuk, S.: On the transversal number and VC-dimension of families of positive homothets of a convex body. Discrete Math. 310(1), 77\u201382 (2010)","journal-title":"Discrete Math."},{"key":"20_CR31","unstructured":"Pach, J.: Decomposition of multiple packing and covering. In: Diskrete Geometrie, vol. 2. Kolloq. Math. Inst. Univ. Salzburg, pp. 169\u2013178 (1980)"},{"issue":"1","key":"20_CR32","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF02187684","volume":"1","author":"J Pach","year":"1986","unstructured":"Pach, J.: Covering the plane with convex polygons. Discrete Comput. Geom. 1(1), 73\u201381 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Pach, J., P\u00e1lv\u00f6lgyi, D., T\u00f3th, G.: Survey on decomposition of multiple coverings. In: Geometry\u2013intuitive, discrete, and convex, 219\u2013257, Bolyai Soc. Math. Stud., 24, J\u00e1nos Bolyai Math. Soc., Budapest (2013)","DOI":"10.1007\/978-3-642-41498-5_9"},{"issue":"3","key":"20_CR34","doi-asserted-by":"publisher","first-page":"451","DOI":"10.4153\/CMB-2009-048-x","volume":"52","author":"J Pach","year":"2009","unstructured":"Pach, J., Tardos, G., T\u00f3th, G.: Indecomposable coverings. Canad. Math. Bull. 52(3), 451\u2013463 (2009)","journal-title":"Canad. Math. Bull."},{"issue":"2","key":"20_CR35","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.comgeo.2008.08.002","volume":"42","author":"J Pach","year":"2009","unstructured":"Pach, J., T\u00f3th, G.: Decomposition of multiple coverings into many parts. Comput. Geom. 42(2), 127\u2013133 (2009)","journal-title":"Comput. Geom."},{"key":"20_CR36","unstructured":"P\u00e1lv\u00f6lgyi, D.: Decomposition of geometric set systems and graphs, Ph.D. thesis, EPFL, Lausanne (2010). \n                      arXiv:1009.4641"},{"issue":"3","key":"20_CR37","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00454-009-9194-y","volume":"44","author":"D P\u00e1lv\u00f6lgyi","year":"2010","unstructured":"P\u00e1lv\u00f6lgyi, D.: Indecomposable coverings with concave polygons. Discrete Comput. Geom. 44(3), 577\u2013588 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"20_CR38","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s00454-009-9133-y","volume":"43","author":"D P\u00e1lv\u00f6lgyi","year":"2010","unstructured":"P\u00e1lv\u00f6lgyi, D., T\u00f3th, G.: Convex polygons are cover-decomposable. Discrete Comput. Geom. 43(3), 483\u2013496 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"20_CR39","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2","volume":"16","author":"J Radhakrishnan","year":"2000","unstructured":"Radhakrishnan, J., Srinivasan, A.: Improved bounds and algorithms for hypergraph 2-coloring. Random Struct. Algorithms 16(1), 4\u201332 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"20_CR40","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00454-007-1345-4","volume":"38","author":"G Tardos","year":"2007","unstructured":"Tardos, G., T\u00f3th, G.: Multiple coverings of the plane with triangles. Discrete Comput. Geom. 38(2), 443\u2013450 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR41","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling, in STOC 2010\u2013Proceedings of the 2010 ACM International Symposium on Theory of Computing pp. 641\u2013647. ACM, New York (2010)","DOI":"10.1145\/1806689.1806777"},{"key":"20_CR42","doi-asserted-by":"crossref","unstructured":"Winkler, P.: Mathematical mind-benders, p. 137. A K Peters, Wellesley, MA: Winkler, P.: Puzzled: covering the plane. Commun. ACM 52(11), 112(2009)","DOI":"10.1145\/1592761.1592786"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:12:13Z","timestamp":1558314733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}