A polynomial-time approximation algorithm for a geometric dispersion problem

M. Benkert, J. Gudmundsson, C. Knauer, R. Oostrum, van, A. Wolff

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)

Abstract

We consider the following packing problem. Let a be a fixed real in (0, 1]. We are given a bounding rectangle ¿ and a set of n possibly intersecting unit disks whose centers lie in ¿. The task is to pack a set of m disjoint disks of radius a into ¿ such that no disk in B intersects a disk in , where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for a = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for a = 2/3 and have shown that the problem cannot be solved in polynomial time for any a > 13/14 unless unless P = NP
Original languageEnglish
Pages (from-to)267-288
JournalInternational Journal of Computational Geometry and Applications
Volume19
Issue number3
DOIs
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'A polynomial-time approximation algorithm for a geometric dispersion problem'. Together they form a unique fingerprint.

Cite this