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 isminimized. Let $Q=\{Q_1,\ldots,Q_n\}$ be a set of polygons or segments in theregion-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 geometricobjects segments and polygons can be models of a point set. We define theuncertain version of the $k$-center problem as a generalization in which theobjective 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 allexact instances of each $Q_i$, respectively. We modify the region-based modelto allow multiple points to be chosen from a region and call the resultingmodel the aggregated uncertainty model. All these problems contain the pointversion as a special case, so they are all NP-hard with a lower bound 1.822. Wegive approximation algorithms for uncertain $k$-center of a set of segments andpolygons. We also have implemented some of our algorithms on a data-set to showour theoretical performance guarantees can be achieved in practice.Comment: Accepted in Fundamenta Informatica