Processing math: 100%
Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Geometric matching and bottleneck problems
Authors:ID Cabello, Sergio (Author)
ID Cheng, Siu-Wing (Author)
ID Cheong, Otfried (Author)
ID Knauer, Christian (Author)
Files:.pdf PDF - Presentation file, download (959,05 KB)
MD5: BD886FA6FD5797E936ECDFECA6F0A6A0
 
URL URL - Source URL, visit https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31
 
Language:English
Typology:1.08 - Published Scientific Conference Contribution
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract: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 pP has an associated supply sp>0, and each rR has an associated demand dr>0. A (many-to-many) matching is a set A of ordered triples (p,r,apr)P×R×R>0 such that pr and the apr's satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing (p,r,apr)Aapr. 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-metric, we can do this in time O(n1+ε) in any fixed dimension, for the L2-metric in the plane in time O(n4/3+ε), for any ε>0.
Keywords:many-to-many matching, bipartite, planar, geometric matching, approximation
Publication status:Published
Publication version:Version of Record
Year of publishing:2024
Number of pages:Str. 31:1-31:15
PID:20.500.12556/DiRROS-20967 New window
UDC:004.42
DOI:10.4230/LIPIcs.SoCG.2024.31 New window
COBISS.SI-ID:218353667 New window
Note:
Publication date in DiRROS:11.12.2024
Views:76
Downloads:33
Metadata:XML DC-XML DC-RDF
:
CABELLO, Sergio, CHENG, Siu-Wing, CHEONG, Otfried and KNAUER, Christian, 2024, Geometric matching and bottleneck problems. In : 40th International Symposium on Computational Geometry [online]. Published Scientific Conference Contribution. Saarbrücken/Wadern. 2024. p. 31:1-31:15. [Accessed 6 January 2025]. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=20967
Copy citation
  
Share:Bookmark and Share


Searching for similar works...Please wait....
Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

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 of publishing:2024
ISBN:978-3-95977-316-4
COBISS.SI-ID:218546691 New window
Collection title:Leibniz international proceedings in informatics
Collection numbering:ǂvol. ǂ293
Collection ISSN:1868-8969

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0218
Name:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih

Funder:Other - Other funder or multiple funders
Funding programme:Research Grants Council, Hong Kong, China
Project number:project no. 16207419

Funder:EC - European Commission
Project number:101071836
Name:KARST: Predicting flow and transport in complex Karst systems
Acronym:KARST

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.

Back