2026-08-25T14:43:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27184 2026-08-25T13:18:17Z ddc:004 open_access

Matching in Geometric Uniform Hypergraphs Katz, Matthew J. Nidam, Yuval Saban, Rachel Sharir, Micha Geometric hypergraphs maximum matching PTAS sparsification local search Let P be a set of n points in ℝ^d, d ≥ 2, and let t ≥ 2 be an integer. Let H_t(P) denote the t-uniform hypergraph on P, whose hyperedges consist of all t-tuples T ⊂ P for which ‖p-q‖ ≤ 1, for any two points p,q ∈ T. A matching in H_t(P) is a collection of vertex-disjoint hyperedges. We present a PTAS for finding a maximum matching in H_t(P). In particular, we present the first PTAS for the well-studied problem known as maximum (vertex-disjoint) triangle packing in unit disk graphs. Our approach consists of a sparsification stage, which replaces P by a subset Q with favorable properties, followed by an implementation of a PTAS for a maximum matching in H_t(Q). The two stages follow the high-level machinery in [Édouard Bonnet et al., 2023] and [Rom Aschner et al., 2013], respectively, but are considerably more involved. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew J. Katz and Yuval Nidam and Rachel Saban and Micha Sharir 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.48 urn:nbn:de:0030-drops-271848 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.48 eng https://creativecommons.org/licenses/by/4.0/legalcode