2 Search Results for "Asano, Tetsuo"

Document
DOI: 10.4230/LIPIcs.SOCG.2015.111
Shortest Path in a Polygon using Sublinear Space

Authors: Sariel Har-Peled

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

Abstract
We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n^2 / m) expected time, assuming m = O(n / log^2 n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linear-programming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel's linear programming algorithm and using pseudo-random sequences.
Cite as

Sariel Har-Peled. Shortest Path in a Polygon using Sublinear Space. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 111-125, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{harpeled:LIPIcs.SOCG.2015.111,
  author =	{Har-Peled, Sariel},
  title =	{{Shortest Path in a Polygon using Sublinear Space}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{111--125},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.111},
  URN =		{urn:nbn:de:0030-drops-50941},
  doi =		{10.4230/LIPIcs.SOCG.2015.111},
  annote =	{Keywords: Shortest path, violator spaces, limited space}
}
Document
DOI: 10.4230/DagSemRep.339
Theoretical Foundations of Computer Vision -- Geometry, Morphology, and Computational Imaging (Dagstuhl Seminar 02151)

Authors: Tetsuo Asano, Reinhard Klette, and Christian Ronse

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Tetsuo Asano, Reinhard Klette, and Christian Ronse. Theoretical Foundations of Computer Vision -- Geometry, Morphology, and Computational Imaging (Dagstuhl Seminar 02151). Dagstuhl Seminar Report 339, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{asano_et_al:DagSemRep.339,
  author =	{Asano, Tetsuo and Klette, Reinhard and Ronse, Christian},
  title =	{{Theoretical Foundations of Computer Vision -- Geometry, Morphology, and Computational Imaging (Dagstuhl Seminar 02151)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{339},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.339},
  URN =		{urn:nbn:de:0030-drops-152211},
  doi =		{10.4230/DagSemRep.339},
}
  • Refine by Author
  • 1 Asano, Tetsuo
  • 1 Har-Peled, Sariel
  • 1 Klette, Reinhard
  • 1 Ronse, Christian

  • Refine by Classification

  • Refine by Keyword
  • 1 Shortest path
  • 1 limited space
  • 1 violator spaces

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2002
  • 1 2015

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