摘要：We study the approximate range searching for three variants of the clustering problem with a set P of n points in d-dimensional Euclidean space and axis-parallel rectangular range queries: the k-median, k-means, and k-center range-clustering query problems. We present data structures and query algorithms that compute (1+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0.
关键词：Approximate clustering; orthogonal range queries
Loading...
