Abstract
Clustering is a fundamental problem of spatiotemporal data analysis. Given a set š³ of n moving entities, each of which corresponds to a sequence of Ļ timestamped points in ā^d, a kclustering of š³ is a partition of š³ into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, kCenter and kMM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worstcase input š³. We show that both problems are NPhard when k is an arbitrary input parameter, even when the motion is restricted to ā. We provide an exact algorithm for the 2MM clustering problem in ā^d that runs in O(Ļ d nĀ²) time. The running time can be improved to O(Ļ n log{n}) when the motion is restricted to ā. We show that the 2Center clustering problem is NPhard in āĀ². Our 2MM clustering algorithm provides a 1.15approximate solution to the 2Center clustering problem in āĀ². Moreover, finding a (1.15Īµ)approximate solution remains NPhard for any Īµ >0. For both the kMM and kCenter clustering problems in ā^d, we provide a 2approximation algorithm that runs in O(Ļ d n k) time.
BibTeX  Entry
@InProceedings{durocher_et_al:LIPIcs:2020:12269,
author = {Stephane Durocher and Md Yeakub Hassan},
title = {{Clustering Moving Entities in Euclidean Space}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {22:122:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12269},
URN = {urn:nbn:de:0030drops122698},
doi = {10.4230/LIPIcs.SWAT.2020.22},
annote = {Keywords: trajectories, clustering, moving entities, kCENTER, algorithms}
}
Keywords: 

trajectories, clustering, moving entities, kCENTER, algorithms 
Collection: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) 
Issue Date: 

2020 
Date of publication: 

12.06.2020 