Geometric matching and bottleneck problems

Cabello, Sergio (author), Cheng, Siu-Wing (author), Cheong, Otfried (author), Knauer, Christian (author)

Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as disks or rectangles, where each $p \in P$ has an associated supply $s_{p} > 0$, and each $r \in R$ has an associated demand $d_{r} > 0$. A (many-to-many) matching is a set ${\mathcal A}$ of ordered triples $(p,r,a_{pr}) \in P \times R \times {\mathbb R}_{>0}$ such that $p \in r$ and the $a_{pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{(p,r,a_{pr}) \in {\mathcal A}} a_{pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3 + \varepsilon})$, for any $\varepsilon > 0$.

• Language: English
• Keywords: many-to-many matching, bipartite, planar, geometric matching, approximation
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: Str. 31:1-31:15
• PID: 20.500.12556/RUL-165635
• UDC: 004.42
• DOI: 10.4230/LIPIcs.SoCG.2024.31
• COBISS.SI-ID: 218353667
• Publication date in RUL: 11.12.2024

Record is a part of a monograph

• Title: 40th International Symposium on Computational Geometry : SoCG 2024, June 11-14, 2024, Athens, Greece
• Editors: Wolfgang Mulzer, Jeff M. Phillips
• Place of publishing: Saarbrücken/Wadern
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Year: 2024
• ISBN: 978-3-95977-316-4
• COBISS.SI-ID: 218546691
• Collection title: Leibniz international proceedings in informatics
• Collection numbering: ǂvol. ǂ293
• Collection ISSN: 1868-8969

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.