{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:38:10Z","timestamp":1725489490499},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_3","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"46-54","source":"Crossref","is-referenced-by-count":0,"title":["Irregularities of Distribution, Derandomization, and Complexity Theory"],"prefix":"10.1007","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P.K. Agarwal","year":"1990","unstructured":"Agarwal, P.K. Partitioning arrangements of lines II: Applications, Disc. Comput. Geom. 5 (1990), 533\u2013573.","journal-title":"Disc. Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Agarwal, P.K. Geometric partitioning and its applications, in Computational Geometry: Papers from the DIMACS Special Year, eds., Goodman, J.E., Pollack, R., Steiger, W., Amer. Math. Soc., 1991.","key":"3_CR2","DOI":"10.1090\/dimacs\/006\/01"},{"doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J. Geometric range searching and its relatives, in Advances in Discrete and Computational Geometry, eds. Chazelle, B., Goodman, J.E., Pollack, R., Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 1\u201356.","key":"3_CR3","DOI":"10.1090\/conm\/223\/03131"},{"unstructured":"Alon, N., Spencer, J.H. The Probabilistic Method, Wiley-Interscience, 1992.","key":"3_CR4"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02392553","volume":"159","author":"J. Beck","year":"1987","unstructured":"Beck, J. Irregularities of distribution, I, Acta Math. 159 (1987), 1\u201349.","journal-title":"Acta Math."},{"doi-asserted-by":"crossref","unstructured":"Beck, J., Chen, W.W.L. Irregularities of Distribution, Cambridge Tracts in Mathematics, 89, Cambridge University Press, 1987.","key":"3_CR6","DOI":"10.1017\/CBO9780511565984"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J. Beck","year":"1981","unstructured":"Beck, J., Fiala, T. \u201cInteger-making\u201d theorems, Discrete Applied Mathematics 3(1981), 1\u20138.","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Beck, J., S\u00f3s, V.T. Discrepancy theory, in Handbook of Combinatorics, Chap. 26, eds., Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L., North-Holland, 1995, pp. 1405\u20131446.","key":"3_CR8"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"637","DOI":"10.2307\/1990891","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B. Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc. 2 (1989), 637\u2013666.","journal-title":"J. Amer. Math. Soc."},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B. Lower bounds for orthogonal range searching: II. The arithmetic model, J. ACM37 (1990), 439\u2013463.","journal-title":"J. ACM"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B. Cutting hyperplanes for divide-and-conquer, Disc. Comput. Geom. 9 (1993), 145\u2013158.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF02573985","volume":"10","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B. An optimal convex hull algorithm in any fixed dimension, Disc. Comput. Geom. 10 (1993), 377\u2013409.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02770864","volume":"17","author":"B. Chazelle","year":"1997","unstructured":"Chazelle, B. Lower bounds for off-line range searching, Disc. Comput. Geom. 17 (1997), 53\u201365.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/S0097539794275665","volume":"27","author":"B. Chazelle","year":"1998","unstructured":"Chazelle, B. A spectral approach to lower bounds with applications to geometric searching, SIAM J. Comput. 27 (1998), 545\u2013556.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B. The Discrepancy Method: Randomness and Complexity, Cambridge University Press, 2000.","key":"3_CR15","DOI":"10.1017\/CBO9780511626371"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J. A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), 229\u2013249.","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B., Lvov, A. A trace bound for the hereditary discrepancy, Proc. 16th Annual ACM Symp. Comput. Geom. (2000), 64\u201369. To appear in Disc. Comput. Geom.","key":"3_CR17","DOI":"10.1145\/336154.336179"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B. Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J. On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms 21 (1996), 579\u2013597.","journal-title":"J. Algorithms"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(86)90037-2","volume":"22","author":"K.L. Clarkson","year":"1986","unstructured":"Clarkson, K.L. Linear programming in O(n * 3d\/2 ) time, Inform. Process. Lett. 22 (1986), 21\u201324.","journal-title":"Inform. Process. Lett."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K.L. Clarkson","year":"1987","unstructured":"Clarkson, K.L. New applications of random sampling in computational geometry, Disc. Comput. Geom. 2 (1987), 195\u2013222.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L. Las Vegas algorithms for linear and integer programming when the dimension is small, J. ACM 42 (1995), 488-499.","journal-title":"J. ACM"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1112\/S0025579300001807","volume":"3","author":"H. Davenport","year":"1956","unstructured":"Davenport, H. Note on irregularities of distribution, Mathematika 3 (1956), 131\u2013135.","journal-title":"Mathematika"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M.E. Dyer","year":"1986","unstructured":"Dyer, M.E. On a multidimensional search technique and its application to the Euclidean one-centre problem, SIAM J. Comput. 15 (1986), 725\u2013738.","journal-title":"SIAM J. Comput."},{"key":"3_CR24","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01587088","volume":"44","author":"M.E. Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M. A randomized algorithm for fixed-dimensional linear programming,tiMathematical Programming 44 (1989), 203\u2013212.","journal-title":"Mathematical Programming"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1111\/j.1749-6632.1960.tb42846.x","volume":"86","author":"J.M. Hammersley","year":"1960","unstructured":"Hammersley, J.M. Monte Carlo methods for solving multivariable problems, Ann. New York Acad. Sci. 86 (1960), 844\u2013874.","journal-title":"Ann. New York Acad. Sci."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E. \u2208-nets and simplex range queries, Disc. Comput. Geom. 2 (1987), 127\u2013151.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J. Construction of \u2208-nets, Disc. Comput. Geom. 5 (1990), 427\u2013448.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR28","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1145\/197405.197408","volume":"26","author":"J. Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J. Geometric range searching, ACM Comput. Surv. 26 (1994), 421\u2013461.","journal-title":"ACM Comput. Surv."},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jcss.1995.1018","volume":"50","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J. Approximations and optimal geometric divide-and-conquer, J. Comput. Syst. Sci. 50 (1995), 203\u2013208.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1006\/jagm.1996.0027","volume":"20","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J. Derandomization in computational geometry, J. Algorithms 20 (1996), 545\u2013580.","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J. Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, 18, Springer, 1999.","key":"3_CR31","DOI":"10.1007\/978-3-642-03942-3"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N. Linear-time algorithms for linear programming in R3 and related problems, SIAM J. Comput. 12 (1983), 759\u2013776.","journal-title":"SIAM J. Comput."},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N. Linear programming in linear time when the dimension is fixed, J. ACM31 (1984), 114\u2013127.","journal-title":"J. ACM"},{"unstructured":"Montgomery, H.L. On irregularities of distribution, in Congress of Number Theory (Zarautz, 1984), Universidad del Pa\u00eds Vasco, Bilbao, 1989, pp. 11\u201327.","key":"3_CR34"},{"doi-asserted-by":"crossref","unstructured":"Montgomery, H.L. Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, CBMS Regional Conference Series in Mathematics, No. 84, Amer. Math. Soc., Providence, 1994.","key":"3_CR35","DOI":"10.1090\/cbms\/084"},{"doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P. Randomized Algorithms, Cambridge University Press, 1995.","key":"3_CR36","DOI":"10.1017\/CBO9780511814075"},{"key":"3_CR37","doi-asserted-by":"crossref","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, CBMS-NSF, SIAM, Philadelphia, PA, 1992."},{"unstructured":"Pach, J., Agarwal, P.K. Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., 1995.","key":"3_CR38"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1112\/S0025579300000541","volume":"1","author":"K.F. Roth","year":"1954","unstructured":"Roth, K.F. On irregularities of distribution, Mathematika 1 (1954), 73\u201379.","journal-title":"Mathematika"},{"key":"3_CR40","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4064\/aa-9-3-257-260","volume":"9","author":"K.F. Roth","year":"1964","unstructured":"Roth, K.F. Remarkc oncerning integer sequences, Acta Arithmetica 9 (1964), 257\u2013260.","journal-title":"Acta Arithmetica"},{"key":"3_CR41","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4064\/aa-9-3-257-260","volume":"9","author":"K.F. Roth","year":"1964","unstructured":"Roth, K.F. Remarkc oncerning integer sequences, Acta Arithmetica 9 (1964), 257\u2013260.","journal-title":"Acta Arithmetica"},{"key":"3_CR42","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/aa-21-1-45-50","volume":"21","author":"W.M. Schmidt","year":"1972","unstructured":"Schmidt, W.M. Irregularities of distribution, VII, Acta Arithmetica 21 (1972), 45\u201350.","journal-title":"Acta Arithmetica"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"Seidel, R. Small-dimensional linear programming and convex hulls made easy, Disc. Comput. Geom. 6 (1991), 423\u2013434.","journal-title":"Disc. Comput. Geom."},{"key":"3_CR44","series-title":"Lect Notes Comput Sci","first-page":"569","volume-title":"A combinatorial bound for linear programming and related problems","author":"M. Sharir","year":"1992","unstructured":"Sharir, M., Welzl, E. A combinatorial bound for linear programming and related problems, Proc. 9th Annual Symp. Theoret. Aspects Comput. Sci., LNCS, 577, Springer-Verlag, 1992, pp. 569\u2013579."},{"key":"3_CR45","doi-asserted-by":"publisher","first-page":"679","DOI":"10.2307\/2000258","volume":"289","author":"J. Spencer","year":"1985","unstructured":"Spencer, J. Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), 679\u2013706.","journal-title":"Trans. Amer. Math. Soc."},{"unstructured":"Spencer, J. Ten Lectures on the Probabilistic Method, CBMS-NSF, SIAM, 1987.","key":"3_CR46"},{"unstructured":"van der Corput, J.G. Verteilungsfunktionen I. Proc. Nederl. Akad. Wetensch. 38 (1935), 813\u2013821.","key":"3_CR47"},{"unstructured":"van der Corput, J.G. Verteilungsfunktionen II. Proc. Nederl. Akad. Wetensch. 38 (1935), 1058\u20131066.","key":"3_CR48"},{"key":"3_CR49","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Ya. On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications 16 (1971), 264\u2013280.","journal-title":"Theory of Probability and its Applications"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:17:12Z","timestamp":1556770632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}