{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T22:05:26Z","timestamp":1768341926775,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,7,25]],"date-time":"2012-07-25T00:00:00Z","timestamp":1343174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00454-012-9443-3","type":"journal-article","created":{"date-parts":[[2012,7,24]],"date-time":"2012-07-24T14:42:56Z","timestamp":1343140976000},"page":"499-517","source":"Crossref","is-referenced-by-count":35,"title":["Simple Proofs of Classical Theorems in Discrete Geometry via the Guth\u2013Katz Polynomial Partitioning Technique"],"prefix":"10.1007","volume":"48","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,7,25]]},"reference":[{"key":"9443_CR1","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/BF02574015","volume":"11","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: On range searching with semialgebraic sets. Discrete Comput. Geom. 11, 393\u2013418 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Sharir, M.: On range searching with semialgebraic sets II. Manuscript (2012)","DOI":"10.1109\/FOCS.2012.32"},{"key":"9443_CR3","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00454-009-9236-5","volume":"44","author":"Y. Akama","year":"2010","unstructured":"Akama, Y., Irie, K., Kawamura, A., Uwano, Y.: VC dimensions of principal component analysis. Discrete Comput. Geom. 44, 589\u2013598 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR4","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/s00454-001-0084-1","volume":"28","author":"B. Aronov","year":"2002","unstructured":"Aronov, B., Sharir, M.: Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom. 28, 475\u2013490 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR5","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00454-003-2853-5","volume":"30","author":"T. Asano","year":"2003","unstructured":"Asano, T., de Berg, M., Cheong, O., Guibas, L.J., Snoeyink, J., Tamaki, H.: Spanning trees crossing few barriers. Discrete Comput. Geom. 30, 591\u2013606 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR6","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05355-3","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2003","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2003)"},{"key":"9443_CR7","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00454-012-9410-z","volume":"47","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M.: Optimal partition trees. Discrete Comput. Geom. 47, 661\u2013690 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR8","volume-title":"Handbook of Data Structures and Applications","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B.: Cuttings. In: Mehta, D., Sahni, S. (eds.) Handbook of Data Structures and Applications. Chapman & Hall\/CRC Press, Boca Raton (2005). Chap.\u00a025"},{"key":"9443_CR9","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom. 4, 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., Welzl, E.: Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5, 99\u2013160 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR11","volume-title":"Using Algebraic Geometry","author":"D. Cox","year":"2004","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Using Algebraic Geometry, 2nd edn. Springer, Heidelberg (2004)","edition":"2"},{"key":"9443_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"D. Cox","year":"2007","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd edn. Springer, Heidelberg (2007)","edition":"3"},{"key":"9443_CR13","volume-title":"Paul Erd\u0151s and His Mathematics","author":"Gy. Elekes","year":"2001","unstructured":"Elekes, Gy.: Sums versus products in number theory, algebra and Erd\u0151s geometry. In: Hal\u00e1sz, G., et al. (eds.) Paul Erd\u0151s and His Mathematics. J.\u00a0Bolyai Math. Soc., Budapest (2001)"},{"key":"9443_CR14","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1017\/S0963548311000137","volume":"20","author":"Gy. Elekes","year":"2011","unstructured":"Elekes, Gy., Sharir, M.: Incidences in three dimensions and distinct distances in the plane. Comb. Probab. Comput. 20, 571\u2013608 (2011). Also in arXiv:1005.0982","journal-title":"Comb. Probab. Comput."},{"key":"9443_CR15","doi-asserted-by":"crossref","first-page":"248","DOI":"10.2307\/2305092","volume":"53","author":"P. Erd\u0151s","year":"1946","unstructured":"Erd\u0151s, P.: On a set of distances of n points. Am. Math. Mon. 53, 248\u2013250 (1946)","journal-title":"Am. Math. Mon."},{"key":"9443_CR16","doi-asserted-by":"crossref","first-page":"2828","DOI":"10.1016\/j.aim.2010.05.015","volume":"225","author":"L. Guth","year":"2010","unstructured":"Guth, L., Katz, N.H.: Algebraic methods in discrete analogs of the Kakeya problem. Adv. Math. 225, 2828\u20132839 (2010). Also in arXiv:0812.1043v1","journal-title":"Adv. Math."},{"key":"9443_CR17","unstructured":"Guth, L., Katz, N.H.: On the Erd\u0151s distinct distances problem in the plane. arXiv:1011.4105"},{"key":"9443_CR18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF01442458","volume":"10","author":"C.G.A. Harnack","year":"1876","unstructured":"Harnack, C.G.A.: \u00dcber Vieltheiligkeit der Ebenen algebraischen Kurven. Math. Ann. 10, 189\u2013199 (1876)","journal-title":"Math. Ann."},{"key":"9443_CR19","unstructured":"Har-Peled, S.: Approximating Spanning Trees with Low Crossing Numbers. Preprint. arXiv:0907.1131"},{"issue":"4","key":"9443_CR20","first-page":"1","volume":"18","author":"A. Iosevich","year":"2011","unstructured":"Iosevich, A., Roche-Newton, O., Rudnev, M.: On an application of Guth\u2013Katz theorem. Math. Res. Lett. A 18(4), 1\u20137 (2011)","journal-title":"Math. Res. Lett. A"},{"key":"9443_CR21","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1017\/S0963548312000144","volume":"21","author":"H. Kaplan","year":"2012","unstructured":"Kaplan, H., Matou\u0161ek, J., Safernov\u00e1, Z., Sharir, M.: Unit distances in three dimensions. Comb. Probab. Comput. 21, 597\u2013610 (2012)","journal-title":"Comb. Probab. Comput."},{"key":"9443_CR22","first-page":"649","volume-title":"Proc. 28th Int. Sympos. on Theoretical Aspects of Computer Science (STACS)","author":"C. Knauer","year":"2011","unstructured":"Knauer, C., Tiwary, H.R., Werner, D.: On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. In: Proc. 28th Int. Sympos. on Theoretical Aspects of Computer Science (STACS), pp. 649\u2013660 (2011)"},{"key":"9443_CR23","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T. K\u0151v\u00e1ri","year":"1954","unstructured":"K\u0151v\u00e1ri, T., S\u00f3s, V., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Coll. Math. 3, 50\u201357 (1954)","journal-title":"Zarankiewicz. Coll. Math."},{"key":"9443_CR24","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9443_CR25","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF02392598","volume":"177","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: Improved upper bounds for approximation by zonotopes. Acta Math. 177, 55\u201373 (1996)","journal-title":"Acta Math."},{"key":"9443_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Heidelberg (2002)"},{"key":"9443_CR27","series-title":"Lectures on Topological Methods in Combinatorics and Geometry Series","volume-title":"Using the Borsuk-Ulam Theorem","author":"J. Matou\u0161ek","year":"2003","unstructured":"Matou\u0161ek, J.: Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry Series. Springer, Heidelberg (2003)"},{"key":"9443_CR28","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/BF01303517","volume":"13","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J., Welzl, E., Wernisch, L.: Discrepancy and \u03b5-approximations for bounded VC-dimension. Combinatorica 13, 455\u2013466 (1993)","journal-title":"Combinatorica"},{"key":"9443_CR29","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J.W. Milnor","year":"1964","unstructured":"Milnor, J.W.: On the Betti numbers of real algebraic varieties. Proc. Am. Math. Soc. 15, 275\u2013280 (1964)","journal-title":"Proc. Am. Math. Soc."},{"key":"9443_CR30","volume-title":"Elements of Algebraic Topology","author":"J.R. Munkres","year":"1984","unstructured":"Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984)"},{"issue":"70","key":"9443_CR31","first-page":"635","volume":"28","author":"O. Oleinik","year":"1951","unstructured":"Oleinik, O.: Estimates of the Betti numbers of real algebraic hypersurfaces. Mat. Sb. 28(70), 635\u2013640 (1951) (in Russian)","journal-title":"Mat. Sb."},{"key":"9443_CR32","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0097-3165(92)90094-B","volume":"59","author":"J. Pach","year":"1992","unstructured":"Pach, J., Sharir, M.: Repeated angles in the plane and related problems. J. Comb. Theory, Ser. A 59, 12\u201322 (1992)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9443_CR33","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1017\/S0963548397003192","volume":"7","author":"J. Pach","year":"1998","unstructured":"Pach, J., Sharir, M.: On the number of incidences between points and curves. Comb. Probab. Comput. 7, 121\u2013127 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"9443_CR34","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1090\/conm\/342\/06151","volume-title":"Towards a Theory of Geometric Graphs","author":"J. Pach","year":"2004","unstructured":"Pach, J., Sharir, M.: Geometric incidences. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics, vol. 342, pp. 185\u2013223. AMS, Providence (2004)"},{"key":"9443_CR35","first-page":"389","volume":"13","author":"I.G. Petrovski\u0131\u030c","year":"1949","unstructured":"Petrovski\u0131\u030c, I.G., Oleinik, O.A.: On the topology of real algebraic surfaces. Izv. Akad. Nauk SSSR, Ser. Mat. 13, 389\u2013402 (1949) (in Russian)","journal-title":"Izv. Akad. Nauk SSSR, Ser. Mat."},{"key":"9443_CR36","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1090\/S0002-9904-1942-07811-6","volume":"48","author":"A. Sard","year":"1942","unstructured":"Sard, A.: The measure of the critical values of differentiable maps. Bull. Am. Math. Soc. 48, 883\u2013890 (1942)","journal-title":"Bull. Am. Math. Soc."},{"key":"9443_CR37","doi-asserted-by":"crossref","unstructured":"Solymosi, J., Tao, T.: An incidence theorem in higher dimensions (2012). arXiv:1103.2926v4","DOI":"10.1007\/s00454-012-9420-x"},{"key":"9443_CR38","volume-title":"Lectures on Differential Geometry","author":"S. Sternberg","year":"1964","unstructured":"Sternberg, S.: Lectures on Differential Geometry. Prentice-Hall, Englewood Cliffs (1964)"},{"key":"9443_CR39","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1215\/S0012-7094-42-00925-6","volume":"9","author":"A.H. Stone","year":"1942","unstructured":"Stone, A.H., Tukey, J.W.: Generalized sandwich theorems. Duke Math. J. 9, 356\u2013359 (1942)","journal-title":"Duke Math. J."},{"key":"9443_CR40","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1017\/S0963548397002976","volume":"6","author":"L. Sz\u00e9kely","year":"1997","unstructured":"Sz\u00e9kely, L.: Crossing numbers and hard Erd\u0151s problems in discrete geometry. Comb. Probab. Comput. 6, 353\u2013358 (1997)","journal-title":"Comb. Probab. Comput."},{"key":"9443_CR41","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02579194","volume":"3","author":"E. Szemer\u00e9di","year":"1983","unstructured":"Szemer\u00e9di, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3, 381\u2013392 (1983)","journal-title":"Combinatorica"},{"key":"9443_CR42","volume-title":"Differential and Combinatorial Topology","author":"R. Thom","year":"1965","unstructured":"Thom, R.: On the homology of real algebraic varieties (in French). In: Cairns, S.S. (ed.) Differential and Combinatorial Topology. Princeton Univ. Press, Princeton (1965)"},{"key":"9443_CR43","unstructured":"Valtr, P.: Strictly convex norms allowing many unit distances and related touching questions. Manuscript, Charles University, Prague (2005)"},{"key":"9443_CR44","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"H.E. Warren","year":"1968","unstructured":"Warren, H.E.: Lower bound for approximation by nonlinear manifolds. Trans. Am. Math. Soc. 133, 167\u2013178 (1968)","journal-title":"Trans. Am. Math. Soc."},{"key":"9443_CR45","series-title":"ACM Sympos. Comput. Geom.","first-page":"23","volume-title":"Proc. 4th Annu","author":"E. Welzl","year":"1988","unstructured":"Welzl, E.: Partition trees for triangle counting and other range searching problems. In: Proc. 4th Annu. ACM Sympos. Comput. Geom., pp. 23\u201333 (1988)"},{"key":"9443_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/3-540-55488-2_30","volume-title":"Data Structures and Efficient Algorithms","author":"E. Welzl","year":"1992","unstructured":"Welzl, E.: On spanning trees with low crossing numbers. In: Data Structures and Efficient Algorithms. Lecture Notes in Computer Science, vol. 594, pp. 233\u2013249. Springer, Heidelberg (1992)"},{"key":"9443_CR47","unstructured":"Zahl, J.: An improved bound on the number of point-surface incidences in three dimensions (2011). First posted (v1) April 26, 2011, revised and corrected (v2) September 22. arXiv:1104.4987"},{"key":"9443_CR48","unstructured":"Zahl, J.: A Szemer\u00e9di\u2013Trotter type theorem in \u211d4. arXiv:1203.4600 (March) 2012"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9443-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9443-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9443-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T16:39:41Z","timestamp":1561999181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9443-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,25]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9443"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9443-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,25]]}}}