On Clusters that are Separated but Large

2021/06/09 by Har-Peled, Sariel, Rogge, Joseph
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2106.05363

Abstract

\renewcommand\ReℝGiven a set P of n points in \Re^d, consider the problem of computing k subsets of P that form clusters that are well-separated from each other, and each of them is large (cardinality wise). We provide tight upper and lower bounds, and corresponding algorithms, on the quality of separation, and the size of the clusters that can be computed, as a function of n,d,k,s, and Φ, where s is the desired separation, and Φ is the spread of the point set P.

Related

• Polylogarithmic Sketches for Clustering
• Good Clusterings Have Large Volume
• A bound on partitioning clusters
• Coresets for k-median clustering under Fréchet and Hausdorff distances
• Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal