DROPS

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.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}
}

Search Results

Documents authored by Voronov, Roman

Geometric Secluded Paths and Planar Satisfiability

Abstract

Cite as

Thanks for your feedback!

Could not send message