2026-07-22T14:05:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2464 2024-03-06T10:33:23Z ddc:004 open_access

Dispersion in Unit Disks Dumitrescu, Adrian Jiang, Minghui Dispersion problem linear programming approximation algorithm We present two new approximation algorithms with (improved) constant ratios for selecting $n$ points in $n$ unit disks such that the minimum pairwise distance among the points is maximized. (I) A very simple $O(n \log{n})$-time algorithm with ratio $0.5110$ for disjoint unit disks. In combination with an algorithm of Cabello~\cite{Ca07}, it yields a $O(n^2)$-time algorithm with ratio of $0.4487$ for dispersion in $n$ not necessarily disjoint unit disks. (II) A more sophisticated LP-based algorithm with ratio $0.6495$ for disjoint unit disks that uses a linear number of variables and constraints, and runs in polynomial time. The algorithm introduces a novel technique which combines linear programming and projections for approximating distances. The previous best approximation ratio for disjoint unit disks was $\frac{1}{2}$. Our results give a partial answer to an open question raised by Cabello~\cite{Ca07}, who asked whether $\frac{1}{2}$ could be improved. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adrian Dumitrescu and Minghui Jiang 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2464 urn:nbn:de:0030-drops-24646 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2464 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode