License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.22
URN: urn:nbn:de:0030-drops-122698
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12269/
Go to the corresponding LIPIcs Volume Portal


Durocher, Stephane ; Hassan, Md Yeakub

Clustering Moving Entities in Euclidean Space

pdf-format:
LIPIcs-SWAT-2020-22.pdf (0.8 MB)


Abstract

Clustering is a fundamental problem of spatio-temporal data analysis. Given a set š’³ of n moving entities, each of which corresponds to a sequence of Ļ„ time-stamped points in ā„^d, a k-clustering of š’³ is a partition of š’³ into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, k-Center and k-MM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worst-case input š’³. We show that both problems are NP-hard when k is an arbitrary input parameter, even when the motion is restricted to ā„. We provide an exact algorithm for the 2-MM 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 2-Center clustering problem is NP-hard in ā„Ā². Our 2-MM clustering algorithm provides a 1.15-approximate solution to the 2-Center clustering problem in ā„Ā². Moreover, finding a (1.15-Īµ)-approximate solution remains NP-hard for any Īµ >0. For both the k-MM and k-Center clustering problems in ā„^d, we provide a 2-approximation 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:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12269},
  URN =		{urn:nbn:de:0030-drops-122698},
  doi =		{10.4230/LIPIcs.SWAT.2020.22},
  annote =	{Keywords: trajectories, clustering, moving entities, k-CENTER, algorithms}
}

Keywords: trajectories, clustering, moving entities, k-CENTER, algorithms
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI