DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.48

Matching in Geometric Uniform Hypergraphs

Authors: Matthew J. Katz, Yuval Nidam, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Matthew J. Katz, Yuval Nidam, Rachel Saban, and Micha Sharir. Matching in Geometric Uniform Hypergraphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{katz_et_al:LIPIcs.ESA.2026.48,
  author =	{Katz, Matthew J. and Nidam, Yuval and Saban, Rachel and Sharir, Micha},
  title =	{{Matching in Geometric Uniform Hypergraphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.48},
  URN =		{urn:nbn:de:0030-drops-271848},
  doi =		{10.4230/LIPIcs.ESA.2026.48},
  annote =	{Keywords: Geometric hypergraphs, maximum matching, PTAS, sparsification, local search}
}

Search Results

Documents authored by Nidam, Yuval

Matching in Geometric Uniform Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message