{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:40Z","timestamp":1740109600119,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:00:00Z","timestamp":1716422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:00:00Z","timestamp":1716422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1907400","CCF-2224271"],"award-info":[{"award-number":["CCF-1907400","CCF-2224271"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00454-024-00648-8","type":"journal-article","created":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T14:02:55Z","timestamp":1716472975000},"page":"466-489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings"],"prefix":"10.1007","volume":"73","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-9635","authenticated-orcid":false,"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,23]]},"reference":[{"key":"648_CR1","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Har-Peled, S.: On the number of incidences when avoiding an induced biclique in geometric settings. In: Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1398\u20131413 (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch50","DOI":"10.1137\/1.9781611977554.ch50"},{"issue":"3","key":"648_CR2","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1017\/S0963548397002976","volume":"6","author":"LA Sz\u00e9kely","year":"1997","unstructured":"Sz\u00e9kely, L.A.: Crossing numbers and hard Erdos problems in discrete geometry. Comb. Probab. Comput. 6(3), 353\u2013358 (1997). https:\/\/doi.org\/10.1017\/S0963548397002976","journal-title":"Comb. Probab. Comput."},{"key":"648_CR3","first-page":"1","volume-title":"Advances in Discrete and Computational Geometry","author":"PK Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry, pp. 1\u201356. AMS Press, New York (1999)"},{"key":"648_CR4","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Zheng, D.W.: Hopcroft\u2019s problem, log-star shaving, 2D fractional cascading, and decision trees. In: Proceedings of the 33th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 190\u2013210 (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.10","DOI":"10.1137\/1.9781611977073.10"},{"issue":"6","key":"648_CR5","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4171\/jems\/705","volume":"19","author":"J Fox","year":"2017","unstructured":"Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz\u2019 problem. J. Eur. Math. Soc. 19(6), 1785\u20131810 (2017). https:\/\/doi.org\/10.4171\/jems\/705","journal-title":"J. Eur. Math. Soc."},{"key":"648_CR6","unstructured":"Janzer, O., Pohoata, C.: On the Zarankiewicz problem for graphs with bounded VC-dimension. arXiv Preprint (2021). arXiv:2009.00130"},{"issue":"4","key":"648_CR7","doi-asserted-by":"publisher","first-page":"1864","DOI":"10.1137\/18M1221606","volume":"33","author":"T Do","year":"2019","unstructured":"Do, T.: Representation complexities of semi-algebraic graphs. SIAM J. Discret. Math. 33(4), 1864\u20131877 (2019). https:\/\/doi.org\/10.1137\/18M1221606","journal-title":"SIAM J. Discret. Math."},{"key":"648_CR8","unstructured":"Frankl, N., Kupavskii, A.: On the Erd\u0151s\u2013Purdy problem and the Zarankiewitz problem for semialgebraic graphs. CoRR (2021). arXiv:2112.10245"},{"key":"648_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1017\/fms.2021.52","volume":"9","author":"A Basit","year":"2021","unstructured":"Basit, A., Chernikov, A., Starchenko, S., Tao, T., Tran, C.-M.: Zarankiewicz\u2019s problem for semilinear hypergraphs. Forum Math. Sigma 9, 59 (2021). https:\/\/doi.org\/10.1017\/fms.2021.52","journal-title":"Forum Math. Sigma"},{"issue":"6","key":"648_CR10","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1017\/S0963548321000171","volume":"30","author":"I Tomon","year":"2021","unstructured":"Tomon, I., Zakharov, D.: Tur\u00e1n-type results for intersection graphs of boxes. Comb. Probab. Comput. 30(6), 982\u2013987 (2021). https:\/\/doi.org\/10.1017\/S0963548321000171","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"648_CR11","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching: I. The reporting case. J. ACM 37(2), 200\u2013212 (1990). https:\/\/doi.org\/10.1145\/77600.77614","journal-title":"J. ACM"},{"key":"648_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Santa Clara (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"issue":"3","key":"648_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. Theory Appl. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"648_CR14","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Pach, J., Sharir, M.: State of the union\u2014of geometric objects. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys in Discrete and Computational Geometry Twenty Years Later. Contemporary Mathematics, vol. 453, pp. 9\u201348. American Mathematical Society, New York (2008). https:\/\/doi.org\/10.1090\/conm\/453","DOI":"10.1090\/conm\/453"},{"issue":"2","key":"648_CR15","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014). https:\/\/doi.org\/10.1137\/120891241","journal-title":"SIAM J. Comput."},{"key":"648_CR16","doi-asserted-by":"crossref","unstructured":"Welzl, E.: On spanning trees with low crossing numbers. In: Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative. Lecture Notes in Computer Science, vol. 594, pp. 233\u2013249. Springer, New York (1992). http:\/\/www.inf.ethz.ch\/personal\/emo\/ps-files\/LowCross-LNCS594.ps","DOI":"10.1007\/3-540-55488-2_30"},{"key":"648_CR17","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF02574385","volume":"12","author":"PK Agarwal","year":"1994","unstructured":"Agarwal, P.K., Alon, N., Aronov, B., Suri, S.: Can visibility graphs be represented compactly? Discret. Comput. Geom. 12, 347\u2013365 (1994). https:\/\/doi.org\/10.1007\/BF02574385","journal-title":"Discret. Comput. Geom."},{"key":"648_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discret. Comput. Geom. 8, 315\u2013334 (1992). https:\/\/doi.org\/10.1007\/BF02293051","journal-title":"Discret. Comput. Geom."},{"key":"648_CR19","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discret. Comput. Geom. 10, 157\u2013182 (1993). https:\/\/doi.org\/10.1007\/BF02573972","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"648_CR20","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(3), 229\u2013249 (1990). https:\/\/doi.org\/10.1007\/BF02122778","journal-title":"Combinatorica"},{"key":"648_CR21","unstructured":"Erickson, J.: On the relative complexities of some geometric problems. In: Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG), pp. 85\u201390 (1995). http:\/\/www.cccg.ca\/proceedings\/1995\/cccg1995_0014.pdf"},{"issue":"4","key":"648_CR22","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF02712875","volume":"16","author":"J Erickson","year":"1996","unstructured":"Erickson, J.: New lower bounds for Hopcroft\u2019s problem. Discret. Comput. Geom. 16(4), 389\u2013418 (1996). https:\/\/doi.org\/10.1007\/BF02712875","journal-title":"Discret. Comput. Geom."},{"key":"648_CR23","doi-asserted-by":"publisher","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Text in Mathematics, vol. 212. Springer, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7\/","DOI":"10.1007\/978-1-4613-0039-7\/"},{"key":"648_CR24","doi-asserted-by":"publisher","unstructured":"Chan, T.M.: (Near-)linear-time randomized algorithms for row minima in Monge partial matrices and related problems. In: Proceedings of the 32rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1465\u20131482 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.88","DOI":"10.1137\/1.9781611976465.88"},{"issue":"11","key":"648_CR25","doi-asserted-by":"publisher","first-page":"3192","DOI":"10.1007\/s00453-017-0376-3","volume":"80","author":"P Afshani","year":"2018","unstructured":"Afshani, P., Tsakalidis, K.: Optimal deterministic shallow cuttings for 3-d dominance ranges. Algorithmica 80(11), 3192\u20133206 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0376-3","journal-title":"Algorithmica"},{"key":"648_CR26","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pp. 1\u201310 (2011). https:\/\/doi.org\/10.1145\/1998196.1998198","DOI":"10.1145\/1998196.1998198"},{"key":"648_CR27","doi-asserted-by":"publisher","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pp. 458\u2013463 (2011). https:\/\/doi.org\/10.1145\/1998196.1998271","DOI":"10.1145\/1998196.1998271"},{"key":"648_CR28","doi-asserted-by":"publisher","unstructured":"J\u00f8rgensen, A.G., Larsen, K.G.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 805\u2013813 (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.63","DOI":"10.1137\/1.9781611973082.63"},{"key":"648_CR29","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.aim.2008.06.002","volume":"219","author":"J Fox","year":"2008","unstructured":"Fox, J., Pach, J.: Separator theorems and Tur\u00e1n-type results for planar intersection graphs. Adv. Math. 219, 1070\u20131080 (2008)","journal-title":"Adv. Math."},{"key":"648_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcta.2016.02.001","volume":"141","author":"NH Mustafa","year":"2016","unstructured":"Mustafa, N.H., Pach, J.: On the Zarankiewicz problem for intersection hypergraphs. J. Comb. Theory Ser. A 141, 1\u20137 (2016). https:\/\/doi.org\/10.1016\/j.jcta.2016.02.001","journal-title":"J. Comb. Theory Ser. A"},{"key":"648_CR31","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: Proceedings of 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 198\u2013207 (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892088","DOI":"10.1109\/SFCS.2000.892088"},{"key":"648_CR32","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Nekrich, Y., Rahul, S., Tsakalidis, K.: Orthogonal point location and rectangle stabbing queries in 3-d. In: Proceedings of 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 31\u201313114 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.31","DOI":"10.4230\/LIPIcs.ICALP.2018.31"},{"issue":"1","key":"648_CR33","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K., Har-Peled, S.: On the set multi-cover problem in geometric settings. ACM Trans. Algorithms 9(1), 9 (2012). https:\/\/doi.org\/10.1145\/2390176.2390185","journal-title":"ACM Trans. Algorithms"},{"key":"648_CR34","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"issue":"2","key":"648_CR35","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"TM Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of ($$\\le k$$)-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000). https:\/\/doi.org\/10.1137\/S0097539798349188","journal-title":"SIAM J. Comput."},{"key":"648_CR36","doi-asserted-by":"publisher","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of 15th Annual Symposium on Computational Geometry (SoCG), pp. 390\u2013399 (1999). https:\/\/doi.org\/10.1145\/304893.304993","DOI":"10.1145\/304893.304993"},{"issue":"2","key":"648_CR37","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(02)00294-8","journal-title":"J. Algorithms"},{"issue":"6","key":"648_CR38","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45(6), 891\u2013923 (1998). https:\/\/doi.org\/10.1145\/293347.293348","journal-title":"J. ACM"},{"issue":"2","key":"648_CR39","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: II. Applications. Algorithmica 1(2), 163\u2013191 (1986). https:\/\/doi.org\/10.1007\/BF01840441","journal-title":"Algorithmica"},{"key":"648_CR40","unstructured":"Ishaque, M., Souvaine, D.L., Benbernou, N.M.: Data structures for restricted triangular range searching. In: Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG) (2008)"},{"issue":"4","key":"648_CR41","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1137\/090765092","volume":"40","author":"M Sharir","year":"2011","unstructured":"Sharir, M., Shaul, H.: Semialgebraic range reporting and emptiness searching with applications. SIAM J. Comput. 40(4), 1045\u20131074 (2011). https:\/\/doi.org\/10.1137\/090765092","journal-title":"SIAM J. Comput."},{"key":"648_CR42","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0925-7721(95)00002-X","volume":"5","author":"B Chazelle","year":"1995","unstructured":"Chazelle, B., Rosenberg, B.: Simplex range reporting on a pointer machine. Comput. Geom. 5, 237\u2013247 (1995). https:\/\/doi.org\/10.1016\/0925-7721(95)00002-X","journal-title":"Comput. Geom."},{"key":"648_CR43","doi-asserted-by":"publisher","unstructured":"Afshani, P., Arge, L., Larsen, K.D.: Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In: Proceedings of 26th Annual Symposium on Computational Geometry (SoCG), pp. 240\u2013246 (2010). https:\/\/doi.org\/10.1145\/1810959.1811001","DOI":"10.1145\/1810959.1811001"},{"key":"648_CR44","doi-asserted-by":"publisher","unstructured":"Afshani, P., Cheng, P.: Lower bounds for semialgebraic range searching and stabbing problems. In: Proceedings of 37th International Symposium on Computational Geometry (SoCG), pp. 8\u20131815 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.8","DOI":"10.4230\/LIPIcs.SoCG.2021.8"},{"key":"648_CR45","doi-asserted-by":"publisher","unstructured":"Afshani, P., Cheng, P.: An optimal lower bound for simplex range reporting. In: 6th Symposium on Simplicity in Algorithms (SOSA 2023), pp. 272\u2013277 (2023). https:\/\/doi.org\/10.1137\/1.9781611977585.ch25","DOI":"10.1137\/1.9781611977585.ch25"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00648-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00648-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00648-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T23:52:49Z","timestamp":1739836369000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00648-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,23]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["648"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00648-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,5,23]]},"assertion":[{"value":"24 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}