Connected matchings
We show that each set of n ⩾ 2 points in the plane in general position has a straight-line matching with at least ( 5 n + 1 ) / 27 edges whose segments form a connected set, and such a matching can be computed in O ( n log n ) time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has ⌈ n − 1 3 ⌉ edges. We also consider a colored version, where each edge of the matching should connect points with different colors.
Authors
- Patrick Schnider (ORCID: https://orcid.org/0000-0002-2172-9285)
- Sergio Cabello (ORCID: https://orcid.org/0000-0002-3183-4126)
- Oswin Aichholzer (ORCID: https://orcid.org/0000-0002-2364-0583)
- Viola Mészáros
- Jan Soukup
Publication Details
- Journal
- Computational Geometry
- Published
- 2025-02-26
- DOI
- https://doi.org/10.1016/j.comgeo.2025.102174
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Grantová Agentura České Republiky
- Austrian Science Fund
- Javna Agencija za Raziskovalno Dejavnost RS
- HORIZON EUROPE European Research Council