Geometric Secluded Paths and Planar Satisfiability

DOI10.4230/LIPICS.SOCG.2020.24MaRDI QIDQ6059972zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Valentin Polishchuk, Leonid Sedov, Roman S. Voronov

Publication date 2 November 2023

Full work available at URL https://arxiv.org/abs/1902.06471

zbMATH Keywords

planar satisfiabilityroute planningsecurity/privacyvisibility

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Cryptography (94A60)

Abstract: We consider paths with low emph{exposure} to a 2D polygonal domain, i.e., paths which are seen as little as possible; we differentiate between emph{integral} exposure (when we care about how long the path sees every point of the domain) and emph{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.

Recommendations

• Minimal link visibility paths inside a simple polygon
• Hiding people in polygons
• Secluded path via shortest path

Cited in

(2)

• Tight paths in convex geometric hypergraphs
• Optimizing visibility-based search in polygonal domains

This page was built for publication: Geometric Secluded Paths and Planar Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6059972)