{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:22:43Z","timestamp":1772554963146,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T00:00:00Z","timestamp":1505692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006192","name":"Advanced Scientific Computing Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006192","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Max Planck Center for Visual Computing and Communication"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2017,12,15]]},"abstract":"<jats:p>Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric variants of the Hopcroft-Karp algorithm for bottleneck matching (based on previous work by Efrat el al.) and of the auction algorithm by Bertsekas for Wasserstein distance computation. Both implementations use k-d trees to replace a linear scan with a geometric proximity query. Our interest in this problem stems from the desire to compute distances between persistence diagrams, a problem that comes up frequently in topological data analysis. We show that our geometric matching algorithms lead to a substantial performance gain, both in running time and in memory consumption, over their purely combinatorial counterparts. Moreover, our implementation significantly outperforms the only other implementation available for comparing persistence diagrams.<\/jats:p>","DOI":"10.1145\/3064175","type":"journal-article","created":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T12:20:54Z","timestamp":1505737254000},"page":"1-20","source":"Crossref","is-referenced-by-count":97,"title":["Geometry Helps to Compare Persistence Diagrams"],"prefix":"10.1145","volume":"22","author":[{"given":"Michael","family":"Kerber","sequence":"first","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}]},{"given":"Dmitriy","family":"Morozov","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA, USA"}]},{"given":"Arnur","family":"Nigmetov","sequence":"additional","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}]}],"member":"320","published-online":{"date-parts":[[2017,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2013.10.014"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th Annual Canadian Conference on Computational Geometry (CCCG\u201906)","author":"Pankaj"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591844"},{"key":"e_1_2_1_4_1","volume-title":"WANN: An Implementation of Weighted Nearest Neighbor Search.","author":"Andrievsky Alexander","year":"2008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186476"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02216923"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(05)80062-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/645896.671946"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1276-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-010-9060-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Herbert Edelsbrunner and John Harer. 2010. Computational Topology. An Introduction. American Mathematics Society.  Herbert Edelsbrunner and John Harer. 2010. Computational Topology. An Introduction. American Mathematics Society.","DOI":"10.1090\/mbk\/069"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796607"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0016-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2010.04.016"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44753-6_24"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.9"},{"key":"e_1_2_1_23_1","unstructured":"Dmitriy Morozov. 2010. Dionysus Library for Computing Persistent Homology. Retrieved from mrzv.org\/software\/dionysus.  Dmitriy Morozov. 2010. Dionysus Library for Computing Persistent Homology. Retrieved from mrzv.org\/software\/dionysus."},{"key":"e_1_2_1_24_1","unstructured":"David M. Mount and Sunil Arya. 2010. ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved from http:\/\/www.cs.umd.edu\/&sim;mount\/ANN.  David M. Mount and Sunil Arya. 2010. ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved from http:\/\/www.cs.umd.edu\/&sim;mount\/ANN."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095145"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218080"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3064175","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3064175","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3064175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:15Z","timestamp":1750217775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3064175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,18]]},"references-count":26,"alternative-id":["10.1145\/3064175"],"URL":"https:\/\/doi.org\/10.1145\/3064175","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,18]]}}}