DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2026.36

Exact Subquadratic Algorithm for Many-To-Many Matching on Planar Point Sets with Integer Coordinates

Authors: Seongbin Park and Eunjin Oh

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets R,B ⊂ [Δ]² with |R|+|B| = n, the goal is to select a set of edges between R and B so that every point is incident to at least one edge and the total Euclidean length is minimized. In the general case that R and B are point sets in the plane, the best-known algorithm for the many-to-many matching problem takes Õ(n²) time. We present an exact Õ(n^{1.5} log Δ) time algorithm for point sets in [Δ]². To the best of our knowledge, this is the first subquadratic exact algorithm for planar many-to-many matching under bounded integer coordinates.

Cite as

Seongbin Park and Eunjin Oh. Exact Subquadratic Algorithm for Many-To-Many Matching on Planar Point Sets with Integer Coordinates. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.SWAT.2026.36,
  author =	{Park, Seongbin and Oh, Eunjin},
  title =	{{Exact Subquadratic Algorithm for Many-To-Many Matching on Planar Point Sets with Integer Coordinates}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.36},
  URN =		{urn:nbn:de:0030-drops-260728},
  doi =		{10.4230/LIPIcs.SWAT.2026.36},
  annote =	{Keywords: Edge cover, many-to-many matching, similarity, geometric matching}
}

Search Results

Documents authored by Park, Seongbin

Exact Subquadratic Algorithm for Many-To-Many Matching on Planar Point Sets with Integer Coordinates

Abstract

Cite as

Thanks for your feedback!

Could not send message