2012/09/21 by Kasturi Varadarajan, Xin Xiao, Varadarajan, Kasturi +1 · 3 citations
Engineering · #Industrial Vision Systems and Defect Detection #3D Shape Modeling and Analysis
paper · pdf · doi:10.48550/arxiv.1209.4893
In this article, we study shape fitting problems, ε-coresets, and total sensitivity. We focus on the (j,k)-projective clustering problems, including k-median/k-means, k-line clustering, j-subspace approximation, and the integer (j,k)-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain ε-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the k-median/k-means clustering problems, and obtain positively-weighted ε-coresets for several variants of the (j,k)-projective clustering problem. We also extend an earlier result on ε-coresets for the integer (j,k)-projective clustering problem in fixed dimension to the case of high dimension.