Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2021

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Keikha Vahideh, Aghamolaei Sepideh, Mohades Ali, Ghodsi Mohammad

Fundamenta Informaticae

2021

Vol. 184, nr 3

205--231

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 , . . . , 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 such as 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 for the approximation factor. 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.