2026-07-23T13:53:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14598 2024-03-06T10:54:24Z ddc:004 open_access

Distant Representatives for Rectangles in the Plane Biedl, Therese Lubiw, Anna Naredla, Anurag Murty Ralbovsky, Peter Dominik Stroud, Graeme Distant representatives blocker shapes matching approximation algorithm APX-hardness 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Therese Biedl and Anna Lubiw and Anurag Murty Naredla and Peter Dominik Ralbovsky and Graeme Stroud 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.17 urn:nbn:de:0030-drops-145982 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode