{"docId":9005,"paperId":8776,"url":"https:\/\/fi.episciences.org\/8776","doi":"","journalName":"Fundamenta Informaticae","issn":"0169-2968","eissn":"1875-8681","volume":[{"vid":619,"name":"Volume 184, Issue 3"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"2111.13989","repositoryVersion":2,"repositoryLink":"https:\/\/arxiv.org\/abs\/2111.13989v2","dateSubmitted":"2021-11-30 11:15:45","dateAccepted":"2022-01-11 10:37:59","datePublished":"2022-01-27 12:35:22","titles":["Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model"],"authors":["Keikha, Vahideh","Aghamolaei, Sepideh","Mohades, Ali","Ghodsi, Mohammad"],"abstracts":["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"],"keywords":["Computer Science - Computational Geometry"]}