Dispersion in unit disks

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 1/2. Our results give a partial answer to an open question raised by Cabello \cite{Ca07}, who asked whether 1/2 could be improved.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.299-310, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455298
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 09:38:36
Dernière modification le : mercredi 29 novembre 2017 - 10:26:32
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:50:13

Fichier

dumitrescu.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455298, version 1

Collections

Citation

Adrian Dumitrescu, Minghui Jiang. Dispersion in unit disks. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.299-310, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455298〉

Partager

Métriques

Consultations de la notice

178

Téléchargements de fichiers

179