20.500.12556/DiRROS-20967 Geometric matching and bottleneck problems 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$. many-to-many matching bipartite planar geometric matching approximation true false true Angleški jezik Ni določen Neznano 2024-12-11 10:39:33 2024-12-11 10:39:33 2024-12-12 03:35:31 0000-00-00 00:00:00 2024 0 0 Str. 31:1-31:15 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42 10.4230/LIPIcs.SoCG.2024.31 218353667 218546691 LIPIcs.SoCG.2024.31.pdf LIPIcs.SoCG.2024.31.pdf 1 BD886FA6FD5797E936ECDFECA6F0A6A0 3a6e81681e32811fce4f89f79036f511dcc6646e3408612e8281aedc3d9c013b a87a4525-b7a4-11ef-ba3f-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=29663 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31 1 d570c1a2-b7a3-11ef-ba3f-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=29662 Inštitut za matematiko, fiziko in mehaniko 0 0 0