A polynomial-time approximation algorithm for a geometric dispersion problem

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

doi:10.1142/S0218195909002952

A polynomial-time approximation algorithm for a geometric dispersion problem

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

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

10 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 language	English
Pages (from-to)	267-288
Journal	International Journal of Computational Geometry and Applications
Volume	19
Issue number	3
DOIs	https://doi.org/10.1142/S0218195909002952
Publication status	Published - 2009

Access to Document

10.1142/S0218195909002952

Cite this

@article{aaa3180e4d694bc68905b68b3576ddc7,

title = "A polynomial-time approximation algorithm for a geometric dispersion problem",

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",

author = "M. Benkert and J. Gudmundsson and C. Knauer and {Oostrum, van}, R. and A. Wolff",

year = "2009",

doi = "10.1142/S0218195909002952",

language = "English",

volume = "19",

pages = "267--288",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific",

number = "3",

}

TY - JOUR

T1 - A polynomial-time approximation algorithm for a geometric dispersion problem

AU - Benkert, M.

AU - Gudmundsson, J.

AU - Knauer, C.

AU - Oostrum, van, R.

AU - Wolff, A.

PY - 2009

Y1 - 2009

N2 - 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

AB - 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

U2 - 10.1142/S0218195909002952

DO - 10.1142/S0218195909002952

M3 - Article

SN - 0218-1959

VL - 19

SP - 267

EP - 288

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 3

ER -

A polynomial-time approximation algorithm for a geometric dispersion problem

Abstract

Access to Document

Fingerprint

Cite this