{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:26Z","timestamp":1740109586131,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["StG 757609"],"award-info":[{"award-number":["StG 757609"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1367"],"award-info":[{"award-number":["1367"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0297","J1-9109","J1-8130","J1-8155"],"award-info":[{"award-number":["P1-0297","J1-9109","J1-8130","J1-8155"]}],"id":[{"id":"10.13039\/501100004329","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":[[2023,10]]},"abstract":"Abstract<\/jats:title>LetG<\/jats:italic>be an intersection graph ofn<\/jats:italic>geometric objects in the plane. We show that a maximum matching inG<\/jats:italic>can be found in$$O\\hspace{0.33325pt}(\\rho ^{3\\omega \/2}n^{\\omega \/2})$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>\u03c1<\/mml:mi>3<\/mml:mn>\u03c9<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>n<\/mml:mi>\u03c9<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time with high probability, where$$\\rho $$<\/jats:tex-math>\u03c1<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the density of the geometric objects and$$\\omega >2$$<\/jats:tex-math>\u03c9<\/mml:mi>><\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is a constant such that$$n\\times n$$<\/jats:tex-math>n<\/mml:mi>\u00d7<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>matrices can be multiplied in$$O(n^\\omega )$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>\u03c9<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time. The same result holds for any subgraph of\u00a0G<\/jats:italic>, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in$$O(n^{\\omega \/2})$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>\u03c9<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in$$[1, \\Psi ]$$<\/jats:tex-math>[<\/mml:mo>1<\/mml:mn>,<\/mml:mo>\u03a8<\/mml:mi>]<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>can be found in$$O\\hspace{0.33325pt}(\\Psi ^6\\log ^{11}\\hspace{-0.55542pt}n + \\Psi ^{12 \\omega } n^{\\omega \/2})$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>\u03a8<\/mml:mi>6<\/mml:mn><\/mml:msup>log<\/mml:mo>11<\/mml:mn><\/mml:msup>n<\/mml:mi>+<\/mml:mo>\u03a8<\/mml:mi>12<\/mml:mn>\u03c9<\/mml:mi><\/mml:mrow><\/mml:msup>n<\/mml:mi>\u03c9<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time with high probability.<\/jats:p>","DOI":"10.1007\/s00454-023-00564-3","type":"journal-article","created":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T21:01:23Z","timestamp":1694293283000},"page":"550-579","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Matchings in Geometric Intersection Graphs"],"prefix":"10.1007","volume":"70","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,9]]},"reference":[{"issue":"4","key":"564_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606\u2013635 (2004)","journal-title":"J. ACM"},{"issue":"4","key":"564_CR2","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"PK Agarwal","year":"1993","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Ray shooting and parametric search. SIAM J. Comput. 22(4), 794\u2013806 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"564_CR3","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134\u2013151 (2004)","journal-title":"J. Algorithms"},{"key":"564_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R.: Matrix sparsification and nested dissection over arbitrary fields. J.\u00a0ACM 60(4), #\u00a025 (2013)","DOI":"10.1145\/2508028.2505989"},{"issue":"9","key":"564_CR5","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Computers 28(9), 643\u2013647 (1979)","journal-title":"IEEE Trans. Computers"},{"key":"564_CR6","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., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)"},{"issue":"1","key":"564_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00453-002-0961-x","volume":"34","author":"M de Berg","year":"2002","unstructured":"de Berg, M., van der Stappen, A.F., Vleugels, J., Katz, M.J.: Realistic input models for geometric algorithms. Algorithmica 34(1), 81\u201397 (2002)","journal-title":"Algorithmica"},{"key":"564_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"JR Bunch","year":"1974","unstructured":"Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Math. Comp. 28, 231\u2013236 (1974)","journal-title":"Math. Comp."},{"issue":"3","key":"564_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"HN Djidjev","year":"1997","unstructured":"Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Inform. 34(3), 231\u2013243 (1997)","journal-title":"Acta Inform."},{"issue":"4\u20135","key":"564_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0020-0190(81)90053-3","volume":"13","author":"H Edelsbrunner","year":"1981","unstructured":"Edelsbrunner, H., Maurer, H.A.: On the intersection of orthogonal objects. Inf. Process. Lett. 13(4\u20135), 177\u2013181 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"564_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","volume":"31","author":"A Efrat","year":"2001","unstructured":"Efrat, A., Itai, A., Katz, M.J.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1\u201328 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"564_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.3233\/FI-1995-2241","volume":"22","author":"D Eppstein","year":"1995","unstructured":"Eppstein, D., Miller, G.L., Teng, S.-H.: A deterministic linear time algorithm for geometric separators and its applications. Fundam. Inform. 22(4), 309\u2013329 (1995)","journal-title":"Fundam. Inform."},{"key":"564_CR13","doi-asserted-by":"crossref","unstructured":"Gao, J., Guibas, L.: Geometric algorithms for sensor networks. Philos. Trans. R. Soc. Lond. Ser.\u00a0A Math. Phys. Eng. Sci. 370(1958), 27\u201351 (2011)","DOI":"10.1098\/rsta.2011.0215"},{"issue":"4","key":"564_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF01396660","volume":"50","author":"JR Gilbert","year":"1986","unstructured":"Gilbert, J.R., Tarjan, R.E.: The analysis of a nested dissection algorithm. Numer. Math. 50(4), 377\u2013404 (1986)","journal-title":"Numer. Math."},{"issue":"6","key":"564_CR15","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1137\/16M1079336","volume":"46","author":"S Har-Peled","year":"2017","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput. 46(6), 1712\u20131744 (2017)","journal-title":"SIAM J. Comput."},{"key":"564_CR16","doi-asserted-by":"crossref","unstructured":"Huson, M.L., Sen, A.: Broadcast scheduling algorithms for radio networks. In: Military Communications Conference (San Diego 1995), vol.\u00a02, pp. 647\u2013651. IEEE (1995)","DOI":"10.1109\/MILCOM.1995.483546"},{"issue":"1","key":"564_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0196-6774(82)90007-4","volume":"3","author":"OH Ibarra","year":"1982","unstructured":"Ibarra, O.H., Moran, S., Hui, R.: A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algorithms 3(1), 45\u201356 (1982)","journal-title":"J. Algorithms"},{"key":"564_CR18","unstructured":"Kaplan, H., Klost, K., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Triangles and girth in disk graphs and transmission graphs. In: 27th Annual European Symposium on Algorithms (Munich\/Garching 2019). Leibniz Int. Proc. Inform., vol. 144, #\u00a064. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"3","key":"564_CR19","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1007\/s00454-020-00243-7","volume":"64","author":"H Kaplan","year":"2020","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discrete Comput. Geom. 64(3), 838\u2013904 (2020)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"564_CR20","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/s11276-006-9856-0","volume":"13","author":"S Kumar","year":"2007","unstructured":"Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. Wireless Networks 13(6), 817\u2013834 (2007)","journal-title":"Wireless Networks"},{"issue":"2","key":"564_CR21","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"564_CR22","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"564_CR23","doi-asserted-by":"crossref","unstructured":"Liu, C.-H.: Nearly optimal planar k nearest neighbors queries under general distance functions. SIAM J. Comput. 51(3), 723\u2013765 (2022)","DOI":"10.1137\/20M1388371"},{"key":"564_CR24","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Navigating central path with electrical flows: From flows to matchings, and back. In: 54th Annual Symposium on Foundations of Computer Science (Berkeley 2013), pp. 253\u2013262. IEEE (2013)","DOI":"10.1109\/FOCS.2013.35"},{"key":"564_CR25","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|V|}\\cdot |E|)$$ algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science (Syracuse 1980), pp. 17\u201327. IEEE (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"1","key":"564_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"GL Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"564_CR27","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: 45th Symposium on Foundations of Computer Science (Rome 2004), pp. 248\u2013255. IEEE (2004)","DOI":"10.1007\/978-3-540-30140-0_48"},{"issue":"1","key":"564_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-005-1187-5","volume":"45","author":"M Mucha","year":"2006","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via Gaussian elimination. Algorithmica 45(1), 3\u201320 (2006)","journal-title":"Algorithmica"},{"key":"564_CR29","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Hoboken (1994)"},{"issue":"4","key":"564_CR30","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"MO Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. J. Algorithms 10(4), 557\u2013567 (1989)","journal-title":"J. Algorithms"},{"key":"564_CR31","doi-asserted-by":"crossref","unstructured":"Smith, W.D., Wormald, N.C.: Geometric separator theorems and applications. In: 39th Annual Symposium on Foundations of Computer Science (Palo Alto 1998), pp. 232\u2013243. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743449"},{"issue":"6","key":"564_CR32","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0925-7721(93)90007-S","volume":"3","author":"AF van der Stappen","year":"1993","unstructured":"van der Stappen, A.F., Halperin, D., Overmars, M.H.: The complexity of the free space for a robot moving amidst fat obstacles. Comput. Geom. 3(6), 353\u2013373 (1993)","journal-title":"Comput. Geom."},{"key":"564_CR33","unstructured":"Vazirani, V.V.: A simplification of the MV matching algorithm and its proof (2012). arXiv:1210.4594"},{"issue":"3","key":"564_CR34","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"DE Willard","year":"1985","unstructured":"Willard, D.E., Lueker, G.S.: Adding range restriction capability to dynamic data structures. J. ACM 32(3), 597\u2013617 (1985)","journal-title":"J. ACM"},{"key":"564_CR35","unstructured":"Yuster, R., Zwick, U.: Maximum matching in graphs with an excluded minor. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2007), pp. 108\u2013117. SIAM, Philadelphia (2007)"},{"key":"564_CR36","unstructured":"Zhao, F., Guibas, L.: Wireless Sensor Networks: An Information Processing Approach. Elsevier\/Morgan-Kaufmann (2004)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00564-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00564-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00564-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T20:46:30Z","timestamp":1730061990000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00564-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["564"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00564-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,9,9]]},"assertion":[{"value":"11 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}