License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2464
URN: urn:nbn:de:0030-drops-24646
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2464/
Go to the corresponding LIPIcs Volume Portal

Dumitrescu, Adrian ; Jiang, Minghui

Dispersion in Unit Disks

pdf-format:
1001.DumitrescuAdrian.2464.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{dumitrescu_et_al:LIPIcs:2010:2464,
  author =	{Adrian Dumitrescu and Minghui Jiang},
  title =	{{Dispersion in Unit Disks}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{299--310},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2464},
  URN =		{urn:nbn:de:0030-drops-24646},
  doi =		{10.4230/LIPIcs.STACS.2010.2464},
  annote =	{Keywords: Dispersion problem, linear programming, approximation algorithm}
}

Keywords: Dispersion problem, linear programming, approximation algorithm
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI