{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:04Z","timestamp":1740109324744,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Johannes Kepler University Linz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The dispersion of a point set<jats:inline-formula><jats:alternatives><jats:tex-math>$$P\\subset [0,1]^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>P<\/mml:mi><mml:mo>\u2282<\/mml:mo><mml:msup><mml:mrow><mml:mo>[<\/mml:mo><mml:mn>0<\/mml:mn><mml:mo>,<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>]<\/mml:mo><\/mml:mrow><mml:mi>d<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect<jats:italic>P<\/jats:italic>. It was observed only recently that, for any<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon &gt;0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03b5<\/mml:mi><mml:mo>&gt;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, certain randomized constructions provide point sets with dispersion smaller than<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b5<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and number of elements growing only logarithmically in<jats:italic>d<\/jats:italic>. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in<jats:italic>d<\/jats:italic>. Note that, however, the running-time will be super-exponential in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon ^{-1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>\u03b5<\/mml:mi><mml:mrow><mml:mo>-<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certain<jats:italic>k<\/jats:italic>-restriction problems, which are well-known in coding theory.<\/jats:p>","DOI":"10.1007\/s00453-022-00943-x","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T18:03:22Z","timestamp":1645725802000},"page":"1897-1915","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Constructions of High-Dimensional Sets with Small Dispersion"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1120-8467","authenticated-orcid":false,"given":"Mario","family":"Ullrich","sequence":"first","affiliation":[]},{"given":"Jan","family":"Vyb\u00edral","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,24]]},"reference":[{"key":"943_CR1","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.dam.2017.06.008","volume":"230","author":"C Aistleitner","year":"2017","unstructured":"Aistleitner, C., Hinrichs, A., Rudolf, D.: On the size of the largest empty box amidst a point set. Discrete Appl. Math. 230, 146\u2013150 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"943_CR2","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(86)90161-5","volume":"58","author":"N Alon","year":"1986","unstructured":"Alon, N.: Explicit construction of exponential sized families of $$k$$-independent sets. Discrete Math. 58(2), 191\u2013193 (1986)","journal-title":"Discrete Math."},{"issue":"2","key":"943_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N Alon","year":"1992","unstructured":"Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.M.: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theory 38(2), 509\u2013516 (1992)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"943_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for $$k$$-restrictions. ACM Trans. Algorithms 2, 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"943_CR5","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s00365-013-9219-x","volume":"39","author":"M Bachmayr","year":"2014","unstructured":"Bachmayr, M., Dahmen, W., DeVore, R., Grasedyck, L.: Approximation of high-dimensional rank one tensors. Constr. Approx. 39(2), 385\u2013395 (2014)","journal-title":"Constr. Approx."},{"key":"943_CR6","doi-asserted-by":"crossref","unstructured":"Backer, J., Keil, M.: The mono- and bichromatic empty rectangle and square problems in all dimensions. In Proceedings of the 9th Latin American Symposium on Theoritical Informatics, pp. 14\u201425 (2010)","DOI":"10.1007\/978-3-642-12200-2_3"},{"key":"943_CR7","doi-asserted-by":"publisher","unstructured":"Bukh, B., Chao, T.-W.: Empty axis-parallel boxes. In: International Mathematics Research Notices, rnab123 (2021) https:\/\/doi.org\/10.1093\/imrn\/rnab123","DOI":"10.1093\/imrn\/rnab123"},{"issue":"1","key":"943_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Drysdale, R.L., Lee, D.T.: Computing the largest empty rectangle. SIAM J. Comput. 15(1), 300\u2013315 (1986)","journal-title":"SIAM J. Comput."},{"key":"943_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761188","volume-title":"Digital Nets and Sequences","author":"J Dick","year":"2010","unstructured":"Dick, J., Pillichshammer, F.: Digital Nets and Sequences. Cambridge University Press, Cambridge (2010)"},{"key":"943_CR10","doi-asserted-by":"crossref","unstructured":"Dick, J., Pillichshammer, F.: Discrepancy theory and quasi-Monte Carlo integration. In: A Panorama of Discrepancy Theory, Lecture Notes in Mathematics 2107. Springer (2014)","DOI":"10.1007\/978-3-319-04696-9_9"},{"key":"943_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/j.jco.2010.03.004","volume":"26","author":"B Doerr","year":"2010","unstructured":"Doerr, B., Gnewuch, M., Wahlstr\u00f6m, M.: Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. J. Complex. 26, 490\u2013507 (2010)","journal-title":"J. Complex."},{"key":"943_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, C., Gnewuch, M., Wahlstr\u00f6m, M.: Calculation of discrepancy measures and applications. In: A Panorama of Discrepancy Theory, Lecture Notes in Mathematics 2107. Springer (2014)","DOI":"10.1007\/978-3-319-04696-9_10"},{"key":"943_CR13","doi-asserted-by":"crossref","unstructured":"Drmota, M., Tichy, R.F.: Sequences, discrepancies and applications. In: Lecture Notes in Mathematics, vol. 1651. Springer (1997)","DOI":"10.1007\/BFb0093404"},{"issue":"4","key":"943_CR14","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1017\/S0963548313000187","volume":"22","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Jiang, M.: Maximal empty boxes amidst random points. Combin. Probab. Comput. 22(4), 477\u2013498 (2013)","journal-title":"Combin. Probab. Comput."},{"issue":"2","key":"943_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s00453-012-9635-5","volume":"66","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Jiang, M.: On the largest empty axis-parallel box amidst n points. Algorithmica 66(2), 225\u2013248 (2013)","journal-title":"Algorithmica"},{"key":"943_CR16","unstructured":"Dumitrescu, A., Jiang, M.: Perfect vector sets, properly overlapping partitions, and largest empty box (2016) arXiv:1608.06874v1"},{"issue":"3","key":"943_CR17","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/s00454-017-9871-1","volume":"59","author":"A Dumitrescu","year":"2018","unstructured":"Dumitrescu, A., Jiang, M.: On the number of maximum empty boxes amidst n points. Discrete Comput. Geom. 59(3), 742\u2013756 (2018)","journal-title":"Discrete Comput. Geom."},{"key":"943_CR18","doi-asserted-by":"crossref","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Veli\u010dkovic, B.: Approximations of general independent distributions. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC \u201992), pp. 10\u201316. Association for Computing Machinery, New York","DOI":"10.1145\/129712.129714"},{"key":"943_CR19","doi-asserted-by":"crossref","unstructured":"Gnewuch, M.: Entropy, randomization, derandomization, and discrepancy, Monte Carlo and quasi-Monte Carlo methods 2010. In: Springer Proceedings of the Mathematics Statistics 23. Springer (2012)","DOI":"10.1007\/978-3-642-27440-4_3"},{"key":"943_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jco.2008.10.001","volume":"25","author":"M Gnewuch","year":"2009","unstructured":"Gnewuch, M., Srivastav, A., Winzen, C.: Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems. J. Complex. 25, 115\u2013127 (2009)","journal-title":"J. Complex."},{"key":"943_CR21","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.jco.2018.10.001","volume":"51","author":"A Hinrichs","year":"2019","unstructured":"Hinrichs, A., Prochno, J., Ullrich, M., Vyb\u00edral, J.: The minimal $$k$$-dispersion of point sets in high-dimensions. J. Complex. 51, 68\u201378 (2019)","journal-title":"J. Complex."},{"key":"943_CR22","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","volume":"6","author":"DJ Kleitman","year":"1973","unstructured":"Kleitman, D.J., Spencer, J.H.: Families of $$k$$-independent sets. Discrete Math. 6, 255\u2013262 (1973)","journal-title":"Discrete Math."},{"key":"943_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jco.2017.11.005","volume":"45","author":"D Krieg","year":"2018","unstructured":"Krieg, D.: On the dispersion of sparse grids. J. Complex. 45, 115\u2013119 (2018)","journal-title":"J. Complex."},{"key":"943_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jat.2018.08.002","volume":"237","author":"D Krieg","year":"2019","unstructured":"Krieg, D., Rudolf, D.: Recovery algorithms for high-dimensional rank one tensors. J. Approx. Theory 237, 17\u201329 (2019)","journal-title":"J. Approx. Theory"},{"key":"943_CR25","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200907","volume":"17","author":"N Linial","year":"1997","unstructured":"Linial, N., Luby, M., Saks, M., Zuckerman, D.: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica 17, 215\u2013234 (1997)","journal-title":"Combinatorica"},{"key":"943_CR26","doi-asserted-by":"publisher","unstructured":"Litvak, A.E.: A remark on the minimal dispersion. In: Communications in Contemporary Mathematics, Vol. 23, No. 06. (2021) https:\/\/doi.org\/10.1142\/S0219199720500601","DOI":"10.1142\/S0219199720500601"},{"key":"943_CR27","doi-asserted-by":"crossref","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Explicit expanders and the Ramanujan conjectures. In: Proceedings of the 18th ACM Symposium Theory of Computing, pp 240\u2013246 (1986)","DOI":"10.1145\/12130.12154"},{"issue":"3","key":"943_CR28","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0166-218X(84)90124-0","volume":"8","author":"A Naamad","year":"1984","unstructured":"Naamad, A., Lee, D., Hsu, W.-L.: On the maximum empty rectangle problem. Discrete Appl. Math. 8(3), 267\u2013277 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"943_CR29","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comp. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comp."},{"key":"943_CR30","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: IEEE Proceedings of the 36th Annual Symposium, Foundations of Computer Science, pp. 182\u2013191 (1995)"},{"key":"943_CR31","doi-asserted-by":"crossref","unstructured":"Niederreiter, H.: A quasi-Monte Carlo method for the approximate computation of the extreme values of a function. In: Studies in Pure Mathematics, pp. 523\u2013529. Birkh\u00e4user, Basel (1983)","DOI":"10.1007\/978-3-0348-5438-2_45"},{"key":"943_CR32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081","volume-title":"Random Number Generation and Quasi-Monte Carlo Methods","author":"H Niederreiter","year":"1992","unstructured":"Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1992)"},{"key":"943_CR33","series-title":"Proceedings in Mathematics and Statistics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33507-0_6","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods","author":"E Novak","year":"2016","unstructured":"Novak, E.: Some results on the complexity of numerical integration. In: Cools, R., Nuyens, D. (eds.) Monte Carlo and Quasi-Monte Carlo Methods. Proceedings in Mathematics and Statistics, vol. 163. Springer, Berlin (2016)"},{"issue":"1","key":"943_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00365-015-9282-6","volume":"43","author":"E Novak","year":"2016","unstructured":"Novak, E., Rudolf, D.: Tractability of the approximation of high-dimensional rank one tensors. Constr. Approx. 43(1), 1\u201313 (2016)","journal-title":"Constr. Approx."},{"key":"943_CR35","doi-asserted-by":"crossref","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of Multivariate Problems. Volume II: Standard Information for Functionals. European Mathematical Society Publishing, House, Z\u00fcrich (2010)","DOI":"10.4171\/084"},{"key":"943_CR36","unstructured":"Porat, E., Rothschild, A.: Explicit non-adaptive combinatorial group testing schemes. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol. 5125. Springer, Berlin"},{"key":"943_CR37","first-page":"64","volume":"6","author":"JB Rosser","year":"1962","unstructured":"Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Ill. J. Math. 6, 64\u201397 (1962)","journal-title":"Ill. J. Math."},{"issue":"8\u20139","key":"943_CR38","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0895-7177(96)00036-2","volume":"23","author":"G Rote","year":"1996","unstructured":"Rote, G., Tichy, R.F.: Quasi-Monte Carlo methods and the dispersion of point sequences. Math. Comput. Model. 23(8\u20139), 9\u201323 (1996)","journal-title":"Math. Comput. Model."},{"key":"943_CR39","doi-asserted-by":"crossref","unstructured":"Rudolf, D.: An upper bound of the minimal dispersion via delta covers. In: Contemporary Computational Mathematics: A Celebration of the 80th Birthday of Ian Sloan. Springer (2018)","DOI":"10.1007\/978-3-319-72456-0_50"},{"key":"943_CR40","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1109\/18.6031","volume":"34","author":"G Seroussi","year":"1988","unstructured":"Seroussi, G., Bshouty, N.H.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inform. Theory 34, 513\u2013522 (1988)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"943_CR41","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.ejc.2017.11.006","volume":"69","author":"J Sosnovec","year":"2018","unstructured":"Sosnovec, J.: A note on the minimal dispersion of point sets in the unit cube. Eur. J. Combin. 69, 255\u2013259 (2018)","journal-title":"Eur. J. Combin."},{"key":"943_CR42","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00365-018-9446-2","volume":"48","author":"VN Temlyakov","year":"2018","unstructured":"Temlyakov, V.N.: The Marcinkiewicz-type discretization theorems. Constr. Approx. 48, 337\u2013369 (2018)","journal-title":"Constr. Approx."},{"key":"943_CR43","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jco.2018.02.001","volume":"47","author":"VN Temlyakov","year":"2018","unstructured":"Temlyakov, V.N.: Universal discretization. J. Complex. 47, 97\u2013109 (2018)","journal-title":"J. Complex."},{"key":"943_CR44","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.matcom.2015.12.005","volume":"143","author":"M Ullrich","year":"2018","unstructured":"Ullrich, M.: A lower bound for the dispersion on the torus. Math. Comput. Simul. 143, 186\u2013190 (2018)","journal-title":"Math. Comput. Simul."},{"key":"943_CR45","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.jco.2017.11.003","volume":"45","author":"M Ullrich","year":"2018","unstructured":"Ullrich, M., Vyb\u00edral, J.: An upper bound on the minimal dispersion. J. Complex. 45, 120\u2013126 (2018)","journal-title":"J. Complex."},{"issue":"6","key":"943_CR46","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1287\/opre.48.6.939.12393","volume":"48","author":"S Yakowitz","year":"2000","unstructured":"Yakowitz, S., L\u2019Ecuyer, P., V\u00e1zquez-Abad, F.: Global stochastic optimization with low-dispersion point sets. Oper. Res. 48(6), 939\u2013950 (2000)","journal-title":"Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00943-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00943-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00943-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T05:58:08Z","timestamp":1726725488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00943-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":46,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["943"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00943-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,24]]},"assertion":[{"value":"15 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}