3 Search Results for "van de Kerkhof, Mees"

Document
DOI: 10.4230/LIPIcs.SWAT.2024.18
Dynamic L-Budget Clustering of Curves

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose L-Budget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε^{-1}) space and O^*(L³log(L) + L²log(r^*/r₀)) time where O^* hides factors of ε^{-1}.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong. Dynamic L-Budget Clustering of Curves. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SWAT.2024.18,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson},
  title =	{{Dynamic L-Budget Clustering of Curves}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.18},
  URN =		{urn:nbn:de:0030-drops-200588},
  doi =		{10.4230/LIPIcs.SWAT.2024.18},
  annote =	{Keywords: clustering, streaming algorithm, polygonal curves, Fr\'{e}chet distance, storage efficiency, simplification, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.67
Global Curve Simplification

Authors: Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.
Cite as

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global Curve Simplification. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vandekerkhof_et_al:LIPIcs.ESA.2019.67,
  author =	{van de Kerkhof, Mees and Kostitsyna, Irina and L\"{o}ffler, Maarten and Mirzanezhad, Majid and Wenk, Carola},
  title =	{{Global Curve Simplification}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.67},
  URN =		{urn:nbn:de:0030-drops-111887},
  doi =		{10.4230/LIPIcs.ESA.2019.67},
  annote =	{Keywords: Curve simplification, Fr\'{e}chet distance, Hausdorff distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
  • Refine by Author
  • 2 Kostitsyna, Irina
  • 2 Löffler, Maarten
  • 2 van de Kerkhof, Mees
  • 1 Buchin, Kevin
  • 1 Buchin, Maike
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Fréchet distance
  • 1 Curve simplification
  • 1 Hausdorff distance
  • 1 NP-hardness
  • 1 algorithms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact