3 Search Results for "Talvitie, Topi"

Document
DOI: 10.4230/LIPIcs.SoCG.2020.24
Geometric Secluded Paths and Planar Satisfiability

Authors: Kevin Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov

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

Abstract
We consider paths with low exposure to a 2D polygonal domain, i.e., paths which are seen as little as possible; we differentiate between integral exposure (when we care about how long the path sees every point of the domain) and 0/1 exposure (just counting whether a point is seen by the path or not). For the integral exposure, we give a PTAS for finding the minimum-exposure path between two given points in the domain; for the 0/1 version, we prove that in a simple polygon the shortest path has the minimum exposure, while in domains with holes the problem becomes NP-hard. We also highlight connections of the problem to minimum satisfiability and settle hardness of variants of planar min- and max-SAT.
Cite as

Kevin Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov. Geometric Secluded Paths and Planar Satisfiability. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.24,
  author =	{Buchin, Kevin and Polishchuk, Valentin and Sedov, Leonid and Voronov, Roman},
  title =	{{Geometric Secluded Paths and Planar Satisfiability}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{24:1--24: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.24},
  URN =		{urn:nbn:de:0030-drops-121827},
  doi =		{10.4230/LIPIcs.SoCG.2020.24},
  annote =	{Keywords: Visibility, Route planning, Security/privacy, Planar satisfiability}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.26
Visualizing Quickest Visibility Maps

Authors: Topi Talvitie

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

Abstract
Consider the following modification to the shortest path query problem in polygonal domains: instead of finding shortest path to a query point q, we find the shortest path to any point that sees q. We present an interactive visualization applet visualizing these quickest visibility paths. The applet also visualizes quickest visibility maps, that is the subdivision of the domain into cells by the quickest visibility path structure.
Cite as

Topi Talvitie. Visualizing Quickest Visibility Maps. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 26-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{talvitie:LIPIcs.SOCG.2015.26,
  author =	{Talvitie, Topi},
  title =	{{Visualizing Quickest Visibility Maps}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{26--28},
  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.26},
  URN =		{urn:nbn:de:0030-drops-50906},
  doi =		{10.4230/LIPIcs.SOCG.2015.26},
  annote =	{Keywords: path planning, visibility}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.658
Shortest Path to a Segment and Quickest Visibility Queries

Authors: Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie

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

Abstract
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
Cite as

Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest Path to a Segment and Quickest Visibility Queries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 658-673, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SOCG.2015.658,
  author =	{Arkin, Esther M. and Efrat, Alon and Knauer, Christian and Mitchell, Joseph S. B. and Polishchuk, Valentin and Rote, G\"{u}nter and Schlipf, Lena and Talvitie, Topi},
  title =	{{Shortest Path to a Segment and Quickest Visibility Queries}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{658--673},
  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.658},
  URN =		{urn:nbn:de:0030-drops-51474},
  doi =		{10.4230/LIPIcs.SOCG.2015.658},
  annote =	{Keywords: path planning, visibility, query structures and complexity, persistent data structures, continuous Dijkstra}
}
  • Refine by Author
  • 2 Polishchuk, Valentin
  • 2 Talvitie, Topi
  • 1 Arkin, Esther M.
  • 1 Buchin, Kevin
  • 1 Efrat, Alon
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 2 path planning
  • 2 visibility
  • 1 Planar satisfiability
  • 1 Route planning
  • 1 Security/privacy
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2015
  • 1 2020

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