10.46298/fi-2022-8776
https://fi.episciences.org/8776
Keikha, Vahideh
Vahideh
Keikha
Aghamolaei, Sepideh
Sepideh
Aghamolaei
Mohades, Ali
Ali
Mohades
Ghodsi, Mohammad
Mohammad
Ghodsi
Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model
The $k$-center problem is to choose a subset of size $k$ from a set of $n$
points such that the maximum distance from each point to its nearest center is
minimized. Let $Q=\{Q_1,\ldots,Q_n\}$ be a set of polygons or segments in the
region-based uncertainty model, in which each $Q_i$ is an uncertain point,
where the exact locations of the points in $Q_i$ are unknown. The geometric
objects segments and polygons can be models of a point set. We define the
uncertain version of the $k$-center problem as a generalization in which the
objective is to find $k$ points from $Q$ to cover the remaining regions of $Q$
with minimum or maximum radius of the cluster to cover at least one or all
exact instances of each $Q_i$, respectively. We modify the region-based model
to allow multiple points to be chosen from a region and call the resulting
model the aggregated uncertainty model. All these problems contain the point
version as a special case, so they are all NP-hard with a lower bound 1.822. We
give approximation algorithms for uncertain $k$-center of a set of segments and
polygons. We also have implemented some of our algorithms on a data-set to show
our theoretical performance guarantees can be achieved in practice.
Comment: Accepted in Fundamenta Informaticae
episciences.org
Computer Science - Computational Geometry
Attribution 4.0 International (CC BY 4.0)
2022-01-11
2022-01-27
2022-01-27
eng
journal article
arXiv:2111.13989
10.48550/arXiv.2111.13989
1875-8681
https://fi.episciences.org/8776/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 184, Issue 3
Researchers
Students