# Geometric secluded paths and planar satisfiability

arXiv: https://arxiv.org/abs/1902.06471 · HTML: https://mlsanity.com/paper/1902.06471/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2019.

## Built on by (most cited first, 1 of 1)

- [Reducing Nearest Neighbor Training Sets Optimally and Exactly](https://mlsanity.com/paper/2302.02132/) (2023)

## Abstract (arXiv)

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.