Search Results

Documents authored by Langetepe, Elmar

Document
DOI: 10.4230/LIPIcs.SoCG.2022.7
Minimum-Error Triangulations for Sea Surface Reconstruction

Authors: Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al. (Computers & Geosciences, 157:104920, 2021) who have suggested to learn a triangulation D of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by D to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to k-order Delaunay (k-OD) triangulations and used an integer linear program in order to solve the resulting optimization problem. In geometric terms, the input to our problem consists of two sets of points in ℝ² with elevations: a set 𝒮 that is to be triangulated, and a set ℛ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in ℛ to the triangulated surface that is obtained by interpolating elevations of 𝒮 linearly in each triangle. Our goal is to find the triangulation of 𝒮 that has minimum error with respect to ℛ. In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless P = NP. At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to k-OD triangulations for k ≤ 7. In particular, instances for which the number of connected components of the so-called k-OD fixed-edge graph is small can be solved within few seconds.
Cite as

Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin. Minimum-Error Triangulations for Sea Surface Reconstruction. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arutyunova_et_al:LIPIcs.SoCG.2022.7,
  author =	{Arutyunova, Anna and Driemel, Anne and Haunert, Jan-Henrik and Haverkort, Herman and Kusche, J\"{u}rgen and Langetepe, Elmar and Mayer, Philip and Mutzel, Petra and R\"{o}glin, Heiko},
  title =	{{Minimum-Error Triangulations for Sea Surface Reconstruction}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.7},
  URN =		{urn:nbn:de:0030-drops-160155},
  doi =		{10.4230/LIPIcs.SoCG.2022.7},
  annote =	{Keywords: Minimum-Error Triangulation, k-Order Delaunay Triangulations, Data dependent Triangulations, Sea Surface Reconstruction, fixed-Edge Graph}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.19
Optimal Online Escape Path Against a Certificate

Authors: Elmar Langetepe and David Kübel

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
More than fifty years ago Bellman asked for the best escape path within a known forest but for an unknown starting position. This deterministic finite path is the shortest path that leads out of a given environment from any starting point. There are some worst case positions where the full path length is required. Up to now such a fixed ultimate optimal escape path for a known shape for any starting position is only known for some special convex shapes (i.e., circles, strips of a given width, fat convex bodies, some isosceles triangles). Therefore, we introduce a different, simple and intuitive escape path, the so-called certificate path which make use of some additional information w.r.t. the starting point s. This escape path depends on the starting position s and takes the distances from s to the outer boundary of the environment into account. Because of this, in the above convex examples the certificate path always (for any position s) leaves the environment earlier than the ultimate escape path. Next we assume that neither the precise shape of the environment nor the location of the starting point is not known, we have much less information. For a class of environments (convex shapes and shapes with kernel positions) we design an online strategy that always leaves the environment. We show that the path length for leaving the environment is always shorter than 3.318764 the length of the corresponding certificate path. We also give a lower bound of 3.313126 which shows that for the above class of environments the factor 3.318764 is (almost) tight.
Cite as

Elmar Langetepe and David Kübel. Optimal Online Escape Path Against a Certificate. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{langetepe_et_al:LIPIcs.SWAT.2016.19,
  author =	{Langetepe, Elmar and K\"{u}bel, David},
  title =	{{Optimal Online Escape Path Against a Certificate}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.19},
  URN =		{urn:nbn:de:0030-drops-60414},
  doi =		{10.4230/LIPIcs.SWAT.2016.19},
  annote =	{Keywords: Search games, online algorithms, escape path, competitive analysis, spiral conjecture}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.768
A Fire Fighter’s Problem

Authors: Rolf Klein, Elmar Langetepe, and Christos Levcopoulos

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.
Cite as

Rolf Klein, Elmar Langetepe, and Christos Levcopoulos. A Fire Fighter’s Problem. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 768-780, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.SOCG.2015.768,
  author =	{Klein, Rolf and Langetepe, Elmar and Levcopoulos, Christos},
  title =	{{A Fire Fighter’s Problem}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{768--780},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.768},
  URN =		{urn:nbn:de:0030-drops-51044},
  doi =		{10.4230/LIPIcs.SOCG.2015.768},
  annote =	{Keywords: Motion Planning, Dynamic Environments, Spiralling strategies, Lower and upper bounds}
}
Document
DOI: 10.4230/DagSemProc.06421.5
Competitive Online Searching for a Ray in the Plane

Authors: Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal. First, we give a search strategy for a special case of the ray search---the window shopper problem---, where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$.
Cite as

Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive Online Searching for a Ray in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{eubeler_et_al:DagSemProc.06421.5,
  author =	{Eubeler, Andrea and Fleischer, Rudolf and Kamphans, Tom and Klein, Rolf and Langetepe, Elmar and Trippen, Gerhard},
  title =	{{Competitive Online Searching for a Ray in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.5},
  URN =		{urn:nbn:de:0030-drops-8687},
  doi =		{10.4230/DagSemProc.06421.5},
  annote =	{Keywords: Online motion planning, competitive analysis, ray search}
}
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 Imprint Privacy Contact