Samenvatting
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.
| Originele taal-2 | Engels |
|---|---|
| Titel | 36th International Symposium on Computational Geometry, SoCG 2020 |
| Redacteuren | Sergio Cabello, Danny Z. Chen |
| Uitgeverij | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| ISBN van elektronische versie | 9783959771436 |
| DOI's | |
| Status | Gepubliceerd - 1 jun. 2020 |
| Evenement | 36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Zwitserland Duur: 23 jun. 2020 → 26 jun. 2020 |
Publicatie series
| Naam | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 164 |
| ISSN van geprinte versie | 1868-8969 |
Congres
| Congres | 36th International Symposium on Computational Geometry, SoCG 2020 |
|---|---|
| Land/Regio | Zwitserland |
| Stad | Zurich |
| Periode | 23/06/20 → 26/06/20 |
Bibliografische nota
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.
Financiering
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.