Computing k-Centers On a Line
| dc.creator | Brass, Peter | |
| dc.creator | Knauer, Christian | |
| dc.creator | Na, Hyeon-Suk | |
| dc.creator | Shin, Chan-Su | |
| dc.creator | Vigneron, Antoine | |
| dc.date | 2009-02-19 | |
| dc.date.accessioned | 2026-07-07T12:44:06Z | |
| dc.date.available | 2026-07-07T12:44:06Z | |
| dc.description | In this paper we consider several instances of the k-center on a line problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constraint version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, and a polygon. We first consider the simplest version of the problem where the line l is given in advance; we can solve this problem in O(n log^2 n) time. We then investigate the cases where only the orientation of the line l is fixed and where the line l can be arbitrary. We can solve these problems in O(n^2 log^2 n) time and in O(n^4 log^2 n) expected time, respectively. For the last two problems, we present (1 + e)-approximation algorithms, which run in O((1/e) n log^2 n) time and O((1/e^2) n log^2 n) time, respectively. | |
| dc.description | 14 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/0902.3282 | |
| dc.identifier | http://arxiv.org/abs/0902.3282 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/220655 | |
| dc.subject | Computational Geometry | |
| dc.title | Computing k-Centers On a Line | |
| dc.type | text |