{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:47:52Z","timestamp":1725486472161},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540413486"},{"type":"electronic","value":"9783540444114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44411-4_3","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:52:31Z","timestamp":1182207151000},"page":"36-53","source":"Crossref","is-referenced-by-count":0,"title":["The Incompressibility Method"],"prefix":"10.1007","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Vit\u00e1nyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,22]]},"reference":[{"key":"3_CR1","unstructured":"G. Barequet, A lower bound for Heilbronn\u2019s triangle problem in d dimensions. In: Proc. 10th ACM-SIAM Symp. Discrete Algorithms, 1999, 76\u201381. 40, 41"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"A. Berthiaume, W. van Dam, S. Laplante, Quantum Kolmogorov complexity, Proc. 15th IEEE Computational Complexity Conference, 2000, 240\u2013249. 37","DOI":"10.1109\/CCC.2000.856755"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"J. Beck, Almost collinear triples among N points on the plane, in A Tribute to Paul Erd\u0151s, ed. A. Baker, B. Bollobas and A. Hajnal, Cambridge Univ. Press, 1990, pp. 39\u201357. 40","DOI":"10.1017\/CBO9780511983917.005"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"C. Bertram-Kretzberg, T. Hofmeister, H. Lefmann, An algorithm for Heilbronn\u2019s problem, Proc. 3rd Ann. Conf. Comput. and Combinatorics, T. Jiang and D. T. Lee (Eds), 1997, pp. 23\u201331. 40","DOI":"10.1007\/BFb0045069"},{"key":"3_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/3-540-48523-6_19","volume-title":"New applications of the incompressibility method","author":"H. Buhrman","year":"1999","unstructured":"H. Buhrman, T. Jiang, M. Li, and P. Vit\u00e1nyi, New applications of the incompressibility method, pp. 220\u2013229 in the Proceedings of ICALP\u201999, LNCS 1644, Springer-Verlag, Berlin, 1999."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.2307\/2690746","volume":"66","author":"G. Cairns","year":"1993","unstructured":"G. Cairns, M. McIntyre, and J. Strantzen, Geometric proofs of some recent results of Yang Lu, Math. Magazine, 66(1993), 263\u2013265. 40","journal-title":"Math. Magazine"},{"key":"3_CR7","first-page":"1","volume":"440","author":"P. Erd\u0151s","year":"1985","unstructured":"P. Erd\u0151s, Problems and results in combinatorial geometry, In: Discrete Geometry and Convexity, Annals of the New York Academy of Sciences, 440(1985), 1\u201311. 40","journal-title":"Discrete Geometry and Convexity"},{"key":"3_CR8","unstructured":"P. Erd\u0151s and G. Purdy, Extremal problems in combinatorial theory, In: Handbook of Combinatorics, R. L. Graham, M. Gr\u00f6tschel, L. Lov\u00e1sz, Eds., Elsevier\/MIT Press, 1995, pp. 861\u2013862. 40"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.2307\/2687869","volume":"45","author":"M. Goldberg","year":"1972","unstructured":"M. Goldberg, Maximizing the smallest triangle made by N points in a square, Math. Magazine, 45(1972), 135\u2013144. 40","journal-title":"Math. Magazine"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"R. K. Guy, Unsolved Problems in Number Theory, 2nd ed., Springer-Verlag 1994, pp. 242\u2013244. 40","DOI":"10.1007\/978-1-4899-3585-4"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/0022-0000(85)90042-X","volume":"31","author":"J. Incerpi","year":"1985","unstructured":"J. Incerpi and R. Sedgewick, Improved upper bounds on Shellsort, Journal of Computer and System Sciences, 31(1985), 210\u2013224. 47","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<125::AID-RSA6>3.0.CO;2-X","volume":"10","author":"S. Janson","year":"1997","unstructured":"S. Janson and D. E. Knuth, Shellsort with three increments, Random Struct. Alg., 10(1997), 125\u2013142. 47, 51","journal-title":"Random Struct. Alg."},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(99)00184-X","volume":"235","author":"T. Jiang","year":"2000","unstructured":"T. Jiang, M. Li, and P. Vit\u00e1nyi, New applications of the incompressibility method II, Theoretical Computer Science, 235:1(2000), 59\u201370.","journal-title":"Theoretical Computer Science"},{"key":"3_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/3-540-48523-6_42","volume-title":"J. Assoc. Comput. Mach.","author":"T. Jiang","year":"1999","unstructured":"T. Jiang, M. Li, and P. Vit\u00e1nyi, The average-case complexity of Shellsort, Preliminary version, pp. 453\u2013462 in the Proceedings of ICALP\u201999, LNCS 1644, Springer-Verlag, Berlin, 1999. Also: J. Assoc. Comput. Mach., to appear. 37, 51"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"T. Jiang, M. Li, and P. M. B. Vit\u00e1nyi, The Expected Size of Heilbronn\u2019s Triangles, Proc. 14th IEEE Computational Complexity Conference, 1999, 105\u2013113. 37","DOI":"10.1109\/CCC.1999.766269"},{"key":"3_CR16","unstructured":"D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1973(1st Edition), 1998 (2nd Edition). 47, 51"},{"issue":"1","key":"3_CR17","first-page":"1","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov, Three approaches to the quantitative definition of information. Problems Inform. Transmission, 1(1):1\u20137, 1965. 38","journal-title":"Problems Inform. Transmission"},{"issue":"2","key":"3_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1112\/jlms\/s2-24.3.385","volume":"24","author":"J. Koml\u00f3s","year":"1981","unstructured":"J. Koml\u00f3s, J. Pintz, and E. Szemer\u00e9di, On Heilbronn\u2019s triangle problem, J. London Math. Soc., (2) 24(1981), 385\u2013396. 40, 46","journal-title":"J. London Math. Soc."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1112\/jlms\/s2-25.1.13","volume":"25","author":"J. Koml\u00f3s","year":"1982","unstructured":"J. Koml\u00f3s, J. Pintz, and E. Szemer\u00e9di, A lower bound for Heilbronn\u2019s problem, J. London Math. Soc., 25(1982), 13\u201324. 40","journal-title":"J. London Math. Soc."},{"key":"3_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"M. Li and P. M. B. Vit\u00e1nyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 2nd Edition, 1997. 37, 39, 41, 49","edition":"2nd Edition"},{"key":"3_CR21","unstructured":"M. Nielsen, I. Huang, Quantum Computation and Quantum Information, Cambridge University Press, 2000. 37"},{"key":"3_CR22","unstructured":"D. Mackenzie, On a roll, New Scientist, November 6, 1999, 44\u201348. 37, 41"},{"key":"3_CR23","unstructured":"W. Blum, Geometrisch Eingekreist, Die Zeit, April 13, 2000 (#16), p. 40. 37"},{"key":"3_CR24","unstructured":"D. Mackenzie, Le hasard ne joue pas aux de\u2019s, Courrier International, December 23, 1999\u2013January 5, 2000 (#41), p. 477\u2013478. 37"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(85)90158-X","volume":"57","author":"A. M. Odlyzko","year":"1985","unstructured":"A. M. Odlyzko, J. Pintz, and K. B. Stolarsky, Partitions of planar sets into small triangles, Discrete Math., 57(1985), 89\u201397. 40","journal-title":"Discrete Math."},{"issue":"3","key":"3_CR26","first-page":"63","volume":"1","author":"A. Papernov","year":"1965","unstructured":"A. Papernov and G. Stasevich, A method for information sorting in computer memories, Problems Inform. Transmission, 1:3(1965), 63\u201375. 47","journal-title":"Problems Inform. Transmission"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton, B. Poonen and T. Suel, Improved lower bounds for Shellsort, Proc. 33rd IEEE Symp. Foundat. Comput. Sci., pp. 226\u2013235, 1992. 47, 51","DOI":"10.1109\/SFCS.1992.267769"},{"key":"3_CR28","unstructured":"V. R. Pratt, Shellsort and Sorting Networks, Ph.D. Thesis, Stanford Univ., 1972. 47"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1112\/jlms\/s1-26.3.198","volume":"26","author":"K. F. Roth","year":"1951","unstructured":"K. F. Roth, On a problem of Heilbronn, J. London Math Society, 26(1951), 198\u2013204. 40, 41","journal-title":"J. London Math Society"},{"issue":"3","key":"3_CR30","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1112\/plms\/s3-25.2.193","volume":"25","author":"K. F. Roth","year":"1972","unstructured":"K. F. Roth, On a problem of Heilbronn II, Proc. London Math Society, (3) 25(1972), 193\u2013212. 40","journal-title":"Proc. London Math Society"},{"issue":"3","key":"3_CR31","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1112\/plms\/s3-25.3.543","volume":"25","author":"K. F. Roth","year":"1972","unstructured":"K. F. Roth, On a problem of Heilbronn III, Proc. London Math Society, (3) 25(1972), 543\u2013549. 40","journal-title":"Proc. London Math Society"},{"key":"3_CR32","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1090\/pspum\/024\/0335445","volume":"24","author":"K. F. Roth","year":"1973","unstructured":"K. F. Roth, Estimation of the area of the smallest triangle obtained by selecting three out of n points in a disc of unit area, Proc. Symp. Pure Mathematics 24, AMS, Providence, 1973, pp. 251\u2013262. 40","journal-title":"Proc. Symp. Pure Mathematics"},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/0001-8708(76)90100-6","volume":"22","author":"K. F. Roth","year":"1976","unstructured":"K. F. Roth, Developments in Heilbronn\u2019s triangle problem, Advances in Math. 22(1976), 364\u2013385. 40","journal-title":"Advances in Math"},{"issue":"2","key":"3_CR34","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1112\/jlms\/s2-4.3.545","volume":"4","author":"W. M. Schmidt","year":"1972","unstructured":"W. M. Schmidt, On a problem of Heilbronn, J. London Math. Soc., (2) 4(1972), 545\u2013550. 40","journal-title":"J. London Math. Soc."},{"key":"3_CR35","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Analysis of Shellsort and related algorithms","author":"R. Sedgewick","year":"1996","unstructured":"R. Sedgewick, Analysis of Shellsort and related algorithms, Proc. 4th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 1136, Springer-Verlag, Berlin, 1\u201311. 47"},{"key":"3_CR36","unstructured":"R. Sedgewick, Open problems in the analysis of sorting and searching algorithms, Presented at Workshop on Prob. Analysis of Algorithms, Princeton, 1997 ( http:\/\/www.cs.princeton\/ ). 47, 51"},{"issue":"7","key":"3_CR37","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D. L. Shell","year":"1959","unstructured":"D. L. Shell, A high-speed sorting procedure, Commun. ACM, 2:7(1959), 30\u201332. 47","journal-title":"Commun. ACM"},{"key":"3_CR38","first-page":"215","volume":"10","author":"T. Z. Ping","year":"1994","unstructured":"Tian Zheng Ping, On the problem of Heilbronn type, Northeast. Math. J., 10(1994), 215\u2013216. 40","journal-title":"Northeast. Math. J."},{"key":"3_CR39","unstructured":"L. Yang, J. Z. Zhang, and Z. B. Zeng, Heilbronn problem for five points, Int\u2019l Centre Theoret. Physics preprint IC\/91\/252 (1991). 40"},{"key":"3_CR40","first-page":"503","volume":"13","author":"L. Yang","year":"1992","unstructured":"L. Yang, J. Z. Zhang, and Z. B. Zeng, A conjecture on the first several Heilbronn numbers and a computation, Chinese Ann. Math. Ser. A 13(1992) 503\u2013515. 40","journal-title":"Chinese Ann. Math. Ser. A"},{"key":"3_CR41","first-page":"678","volume":"37","author":"L. Yang","year":"1994","unstructured":"L. Yang, J. Z. Zhang, and Z. B. Zeng, On the Heilbronn numbers of triangular regions, Acta Math. Sinica, 37(1994), 678\u2013689. 40","journal-title":"Acta Math. Sinica"},{"key":"3_CR42","doi-asserted-by":"crossref","unstructured":"P. Vit\u00e1nyi, Three approaches to the quantitative definition of information in an individual pure quantum state, Proc. 15th IEEE Computational Complexity Conference, 2000, 263\u2013270. 37","DOI":"10.1109\/CCC.2000.856757"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(80)90003-6","volume":"1","author":"A. C. C. Yao","year":"1980","unstructured":"A. C. C. Yao, An analysis of (h, k, 1)-Shellsort, J. of Algorithms, 1(1980), 14\u201350. 47","journal-title":"J. of Algorithms"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2000: Theory and Practice of Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44411-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T04:23:15Z","timestamp":1556511795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44411-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540413486","9783540444114"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-44411-4_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}