{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,4]],"date-time":"2022-09-04T00:40:17Z","timestamp":1662252017933},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T00:00:00Z","timestamp":1539561600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>Let<jats:italic>C<\/jats:italic>be a bounded convex object in \u211d<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>, and let<jats:italic>P<\/jats:italic>be a set of<jats:italic>n<\/jats:italic>points lying outside<jats:italic>C<\/jats:italic>. Further, let<jats:italic>c<jats:sub>p<\/jats:sub><\/jats:italic>,<jats:italic>c<jats:sub>q<\/jats:sub><\/jats:italic>be two integers with 1 \u2a7d<jats:italic>c<jats:sub>q<\/jats:sub><\/jats:italic>\u2a7d<jats:italic>c<jats:sub>p<\/jats:sub><\/jats:italic>\u2a7d<jats:italic>n<\/jats:italic>- \u230a<jats:italic>d<\/jats:italic>\/2\u230b, such that every<jats:italic>c<jats:sub>p<\/jats:sub><\/jats:italic>+ \u230a<jats:italic>d<\/jats:italic>\/2\u230b points of<jats:italic>P<\/jats:italic>contain a subset of size<jats:italic>c<jats:sub>q<\/jats:sub><\/jats:italic>+ \u230a<jats:italic>d<\/jats:italic>\/2\u230b whose convex hull is disjoint from<jats:italic>C<\/jats:italic>. Then our main theorem states the existence of a partition of<jats:italic>P<\/jats:italic>into a small number of subsets, each of whose convex hulls are disjoint from<jats:italic>C<\/jats:italic>. Our proof is constructive and implies that such a partition can be computed in polynomial time.<\/jats:p><jats:p>In particular, our general theorem implies polynomial bounds for Hadwiger--Debrunner (<jats:italic>p<\/jats:italic>,<jats:italic>q<\/jats:italic>) numbers for balls in \u211d<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>. For example, it follows from our theorem that when<jats:italic>p<\/jats:italic>&gt;<jats:italic>q<\/jats:italic>= (1+\u03b2)\u22c5<jats:italic>d<\/jats:italic>\/2 for \u03b2 &gt; 0, then any set of balls satisfying the (<jats:italic>p<\/jats:italic>,<jats:italic>q<\/jats:italic>)-property can be hit by<jats:italic>O<\/jats:italic>((1+\u03b2)<jats:sup>2<\/jats:sup><jats:italic>d<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>p<\/jats:italic><jats:sup>1+1\/\u03b2<\/jats:sup>log<jats:italic>p<\/jats:italic>) points. This is the first improvement over a nearly 60 year-old exponential bound of roughly<jats:italic>O<\/jats:italic>(2<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>).<\/jats:p><jats:p>Our results also complement the results obtained in a recent work of Keller, Smorodinsky and Tardos where, apart from improvements to the bound on HD(<jats:italic>p<\/jats:italic>,<jats:italic>q<\/jats:italic>) for convex sets in \u211d<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>for various ranges of<jats:italic>p<\/jats:italic>and<jats:italic>q<\/jats:italic>, a polynomial bound is obtained for regions with low union complexity in the plane.<\/jats:p>","DOI":"10.1017\/s0963548318000445","type":"journal-article","created":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T05:34:16Z","timestamp":1539581656000},"page":"473-482","source":"Crossref","is-referenced-by-count":0,"title":["On a Problem of Danzer"],"prefix":"10.1017","volume":"28","author":[{"given":"NABIL H.","family":"MUSTAFA","sequence":"first","affiliation":[]},{"given":"SAURABH","family":"RAY","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,10,15]]},"reference":[{"key":"S0963548318000445_ref8","first-page":"91","volume-title":"Handbook of Discrete and Computational Geometry","author":"Holmsen","year":"2017"},{"key":"S0963548318000445_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"S0963548318000445_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.02.006"},{"key":"S0963548318000445_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.11.019"},{"key":"S0963548318000445_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44479-6_21"},{"key":"S0963548318000445_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.148"},{"key":"S0963548318000445_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0089220"},{"key":"S0963548318000445_ref3","first-page":"5","article-title":"Extension of a theorem of Moon and Moser on complete subgraphs.","volume":"16","author":"de Caen","year":"1983","journal-title":"Ars Combin."},{"key":"S0963548318000445_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"S0963548318000445_ref13","article-title":"A simple proof of optimal epsilon-nets","author":"Mustafa","year":"2017","journal-title":"Combinatorica"},{"key":"S0963548318000445_ref16","first-page":"1241","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mustafa","year":"2017"},{"key":"S0963548318000445_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_36"},{"key":"S0963548318000445_ref18","first-page":"231","volume-title":"Surveys on Discrete and Computational Geometry: Twenty Years Later","author":"Wagner","year":"2008"},{"key":"S0963548318000445_ref6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1515\/crll.1961.208.181","article-title":"\u00dcber Durchschnittseigenschaften n-dimensionaler Kugelfamilien.","volume":"208","author":"Danzer","year":"1961","journal-title":"J. Reine Angew. Math."},{"key":"S0963548318000445_ref5","unstructured":"Danzer L. (1960) \u00dcber zwei Lagerungsprobleme: Abwandlungen einer Vermutung von T. Gallai. PhD thesis, Technische Hochschule M\u00fcnchen."},{"key":"S0963548318000445_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-018-1685-1"},{"key":"S0963548318000445_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_16"},{"key":"S0963548318000445_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(92)90052-M"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,4]],"date-time":"2022-09-04T00:16:40Z","timestamp":1662250600000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000445\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,15]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000445"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000445","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,15]]}}}