Abstract
Let
be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an
time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is
and present a
-factor approximation algorithm. We improve the approximation factor to
for the case where no two disks of distinct color intersect.
be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an
time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is
and present a
-factor approximation algorithm. We improve the approximation factor to
for the case where no two disks of distinct color intersect.
| Original language | English |
|---|---|
| Pages (from-to) | 116-127 |
| Number of pages | 12 |
| Journal | Theoretical Computer Science |
| Volume | 930 |
| DOIs | |
| Publication status | Published - 21 Sept 2022 |
Keywords
- Color spanning circle
- Imprecise points
- Algorithms
- Computational complexity
- CG
- IMP