{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:35Z","timestamp":1787321135278,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer $k$, every finite set of points in $\\mathbb{R}^3$ can be colored with $k$ colors so that every translate of the negative octant containing at least $k^6$ points contains at least one of each color. The best previously known bound was doubly exponential in $k$. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semionline model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.<\/jats:p>","DOI":"10.1137\/140955975","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T12:23:09Z","timestamp":1416313389000},"page":"1948-1959","source":"Crossref","is-referenced-by-count":7,"title":["Making Octants Colorful and Related Covering Decomposition Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kolja","family":"Knauer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"Ueckerdt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,11,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9425-5"},{"key":"atypb2","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons Inc., New York, 2000."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9238-3"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9116-4"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Asinowski, J. Cardinal, N. Cohen, S. Collette, T. Hackl, M. Hoffmann, K. Knauer, S. Langerman, M. Lason\u0301, P. Micek, G. Rote, and T. Ueckerdt,\n                      Coloring hypergraphs induced by dynamic point sets and bottomless rectangles\n                      , in Proceedings of the Workshop on Data Structures and Algorithms (WADS), 2013, pp. 73-84.","DOI":"10.1007\/978-3-642-40104-6_7"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990587"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383375"},{"key":"atypb8","unstructured":"P. Brass, W. Moser, and J. Pach,\n                      Research Problems in Discrete Geometry\n                      , Springer, New York, 2005."},{"key":"atypb9","first-page":"240","volume":"4","author":"Cardinal J.","year":"2013","journal-title":"J. Comput. Geom."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.06.004"},{"key":"atypb11","first-page":"1576","author":"Chan T. M.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20246"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-007-9075-z"},{"key":"atypb15","unstructured":"R. Fulek,\n                      Coloring geometric hypergraph defined by an arrangement of half-planes\n                      , in Proceedings of the Canadian Conference on Computational Geometry (CCCG), 2010, pp. 71-74."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9353-9"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.09.004"},{"key":"atypb18","first-page":"292","author":"Keszegh B.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9377-1"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9582-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.12.001"},{"key":"atypb22","unstructured":"I. Kova\u0301cs,\n                      Indecomposable coverings with homothetic polygons\n                      , CoRR, abs\/1312.4597 (2013)."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"J. Matous\u030cek,\n                      Lectures on Discrete Geometry\n                      , Grad. Texts in Math. 212. Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb24","first-page":"169","author":"Pach J.","year":"1980","journal-title":"Inst. Math. Univ. Salzburg"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187684"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.04.007"},{"key":"atypb27","first-page":"458","author":"Pach J.","year":"2011","journal-title":"New York"},{"key":"atypb28","first-page":"135","author":"Pach J.","year":"2007","journal-title":"Berlin"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.08.002"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9194-y"},{"key":"atypb31","unstructured":"D. Pa\u0301lvo\u0308lgyi,\n                      Indecomposable coverings with unit discs\n                      , CoRR, abs\/1310.6900 (2013)."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-50.7.509"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/050642368"},{"key":"atypb34","first-page":"118","author":"Smorodinsky S.","year":"2010","journal-title":"Berlin"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1345-4"},{"key":"atypb36","first-page":"641","author":"Varadarajan K.","year":"2010","journal-title":"New York"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140955975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:57Z","timestamp":1787317677000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140955975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/140955975"],"URL":"https:\/\/doi.org\/10.1137\/140955975","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}