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.2016.19
URN: urn:nbn:de:0030-drops-60414
Go to the corresponding LIPIcs Volume Portal

Langetepe, Elmar ; K├╝bel, David

Optimal Online Escape Path Against a Certificate

LIPIcs-SWAT-2016-19.pdf (0.6 MB)


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.

BibTeX - Entry

  author =	{Elmar Langetepe and David K{\"u}bel},
  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 =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  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}

Keywords: Search games, online algorithms, escape path, competitive analysis, spiral conjecture
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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