文章基本信息
- 标题：k-Median Clustering Under Discrete Fréchet and Hausdorff Distances
- 本地全文：下载
- 作者：Abhinandan Nath ; Erin Taylor
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：58:1-58:15
- DOI：10.4230/LIPIcs.SoCG.2020.58
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We give the first near-linear time (1+ε)-approximation algorithm for k-median clustering of polygonal trajectories under the discrete Fréchet distance, and the first polynomial time (1+ε)-approximation algorithm for k-median clustering of finite point sets under the Hausdorff distance, provided the cluster centers, ambient dimension, and k are bounded by a constant. The main technique is a general framework for solving clustering problems where the cluster centers are restricted to come from a simpler metric space. We precisely characterize conditions on the simpler metric space of the cluster centers that allow faster (1+ε)-approximations for the k-median problem. We also show that the k-median problem under Hausdorff distance is NP-Hard.
- 关键词：Clustering; k-median; trajectories; point sets; discrete Fréchet distance; Hausdorff distance
