DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2021.17

Distant Representatives for Rectangles in the Plane

Authors: Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L₁, L₂, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).

Cite as

Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Distant Representatives for Rectangles in the Plane. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ESA.2021.17,
  author =	{Biedl, Therese and Lubiw, Anna and Naredla, Anurag Murty and Ralbovsky, Peter Dominik and Stroud, Graeme},
  title =	{{Distant Representatives for Rectangles in the Plane}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.17},
  URN =		{urn:nbn:de:0030-drops-145982},
  doi =		{10.4230/LIPIcs.ESA.2021.17},
  annote =	{Keywords: Distant representatives, blocker shapes, matching, approximation algorithm, APX-hardness}
}

Search Results

Documents authored by Ralbovsky, Peter Dominik

Distant Representatives for Rectangles in the Plane

Abstract

Cite as

Thanks for your feedback!

Could not send message