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.
| Original language | English |
|---|---|
| Title of host publication | 36th International Symposium on Computational Geometry, SoCG 2020 |
| Editors | Sergio Cabello, Danny Z. Chen |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| ISBN (Electronic) | 9783959771436 |
| DOIs | |
| Publication status | Published - 1 Jun 2020 |
| Event | 36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland Duration: 23 Jun 2020 → 26 Jun 2020 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 164 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 36th International Symposium on Computational Geometry, SoCG 2020 |
|---|---|
| Country/Territory | Switzerland |
| City | Zurich |
| Period | 23/06/20 → 26/06/20 |
Bibliographical note
Funding Information:Acknowledgements We thank Mike Paterson for raising the question of finding minimum-exposure paths, and the anonymous reviewers for the comments improving the presentation of the paper; we also acknowledge discussions with Irina Kostitsyna, Joe Mitchell and Topi Talvitie. Part of the work was done at the workshop on Distributed Geometric Algorithms held in the University of Bologna Centre at Bertinoro Aug 25-31, 2019. VP and LS are supported by the Swedish Transport Administration and the Swedish Research Council.
Publisher Copyright:
© Kevin Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
Funding
Acknowledgements We thank Mike Paterson for raising the question of finding minimum-exposure paths, and the anonymous reviewers for the comments improving the presentation of the paper; we also acknowledge discussions with Irina Kostitsyna, Joe Mitchell and Topi Talvitie. Part of the work was done at the workshop on Distributed Geometric Algorithms held in the University of Bologna Centre at Bertinoro Aug 25-31, 2019. VP and LS are supported by the Swedish Transport Administration and the Swedish Research Council.
Keywords
- Planar satisfiability
- Route planning
- Security/privacy
- Visibility