文章基本信息

标题：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