DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.58

k-Median Clustering Under Discrete Fréchet and Hausdorff Distances

Authors: Abhinandan Nath and Erin Taylor

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

Abhinandan Nath and Erin Taylor. k-Median Clustering Under Discrete Fréchet and Hausdorff Distances. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nath_et_al:LIPIcs.SoCG.2020.58,
  author =	{Nath, Abhinandan and Taylor, Erin},
  title =	{{k-Median Clustering Under Discrete Fr\'{e}chet and Hausdorff Distances}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.58},
  URN =		{urn:nbn:de:0030-drops-122161},
  doi =		{10.4230/LIPIcs.SoCG.2020.58},
  annote =	{Keywords: Clustering, k-median, trajectories, point sets, discrete Fr\'{e}chet distance, Hausdorff distance}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.8

Maintaining Reeb Graphs of Triangulated 2-Manifolds

Authors: Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract

Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.

Cite as

Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath. Maintaining Reeb Graphs of Triangulated 2-Manifolds. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2017.8,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Nath, Abhinandan},
  title =	{{Maintaining Reeb Graphs of Triangulated 2-Manifolds}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.8},
  URN =		{urn:nbn:de:0030-drops-84043},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.8},
  annote =	{Keywords: Reeb graphs, 2-manifolds, topological graph theory}
}

Search Results

Documents authored by Nath, Abhinandan

k-Median Clustering Under Discrete Fréchet and Hausdorff Distances

Abstract

Cite as

Maintaining Reeb Graphs of Triangulated 2-Manifolds

Abstract

Cite as

Thanks for your feedback!

Could not send message