Document Open Access Logo

Geometric Secluded Paths and Planar Satisfiability

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.24.pdf
  • Filesize: 0.85 MB
  • 15 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Valentin Polishchuk
  • Communications and Transport Systems, ITN, Linköping University, Sweden
Leonid Sedov
  • Communications and Transport Systems, ITN, Linköping University, Sweden
Roman Voronov
  • Institute of Mathematics and Information Technologies, Petrozavodsk State University, Russia

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.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SoCG.2020.24

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.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Computational geometry
Keywords
  • Visibility
  • Route planning
  • Security/privacy
  • Planar satisfiability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K Agarwal, Kyle Fox, and Oren Salzman. An efficient algorithm for computing high-quality paths amid polygonal obstacles. ACM Transactions on Algorithms (TALG), 14(4):46, 2018. Google Scholar
  2. Lyudmil Aleksandrov, Anil Maheshwari, and J-R Sack. Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM (JACM), 52(1):25-53, 2005. Google Scholar
  3. Esther M Arkin, Alon Efrat, Christian Knauer, Joseph Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest path to a segment and quickest visibility queries. Journal of Computational Geometry, 7(2):77-100, 2016. Special issue on SoCG'15. Google Scholar
  4. Boris Aronov, Alon Efrat, Ming Li, Jie Gao, Joseph SB Mitchell, Valentin Polishchuk, Boyang Wang, Hanyu Quan, and Jiaxin Ding. Are friends of my friends too social? limitations of location privacy in a socially-connected world. In Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 280-289. ACM, 2018. Google Scholar
  5. Boris Aronov, Leonidas J Guibas, Marek Teichmann, and Li Zhang. Visibility queries and maintenance in simple polygons. Discrete & Computational Geometry, 27(4):461-483, 2002. Google Scholar
  6. Kevin A. Buchin, Valentin Polishchuk, Leonid Sedov, and Roman Voronov. Geometric secluded paths and planar satisfiability. CoRR, abs/1902.06471, 2019. URL: http://arxiv.org/abs/1902.06471.
  7. Svante Carlsson, Håkan Jonsson, and Bengt Nilsson. Finding the shortest watchman route in a simple polygon. Discrete & Computational Geometry, 22(3):377-402, 1999. URL: https://doi.org/10.1007/PL00009467.
  8. Shiri Chechik, Matthew P Johnson, Merav Parter, and David Peleg. Secluded connectivity problems. Algorithmica, 79(3):708-741, 2017. Google Scholar
  9. Siu-Wing Cheng, Jiongxin Jin, and Antoine Vigneron. Triangulation refinement and approximate shortest paths in weighted regions. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1626-1640. SIAM, 2014. Google Scholar
  10. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. Approximate shortest paths in anisotropic regions. SIAM Journal on Computing, 38(3):802-824, 2008. Google Scholar
  11. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. Querying approximate shortest paths in anisotropic regions. SIAM Journal on Computing, 39(5):1888-1918, 2010. Google Scholar
  12. Otfried Cheong, Alon Efrat, and Sariel Har-Peled. Finding a guard that sees most and a shop that sells most. Discrete & Computational Geometry, 37(4):545-563, 2007. Google Scholar
  13. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity classifications of boolean constraint satisfaction problems, volume 7. SIAM, 2001. Google Scholar
  14. Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, and Michiel Smid. A note on the unsolvability of the weighted region shortest path problem. Computational Geometry, 47(7):724-727, 2014. Google Scholar
  15. Erik Demaine. Algorithmic lower bounds: Fun with hardness proofs. MIT OCW. Google Scholar
  16. Hristo N Djidjev. Efficient computation of minimum exposure paths in a sensor network field. In International Conference on Distributed Computing in Sensor Systems, pages 295-308. Springer, 2007. Google Scholar
  17. Hao Feng, Lei Luo, Yong Wang, Miao Ye, and Rongsheng Dong. A novel minimal exposure path problem in wireless sensor networks and its solution algorithm. International Journal of Distributed Sensor Networks, 12(8):1550147716664245, 2016. Google Scholar
  18. Fedor V Fomin, Petr A Golovach, Nikolay Karpov, and Alexander S Kulikov. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems, 61(3):795-819, 2017. Google Scholar
  19. Laxmi Gewali, Alex C. Meng, Joseph S. B. Mitchell, and Simeon C. Ntafos. Path planning in 0/1/infinity weighted regions with applications. In Herbert Edelsbrunner, editor, Proceedings of the Fourth Annual Symposium on Computational Geometry, Urbana-Champaign, IL, USA, June 6-8, 1988, pages 266-278. ACM, 1988. Google Scholar
  20. Subir Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  21. J.E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. Discrete Mathematics and Its Applications. Taylor & Francis, 2nd edition, 2004. Google Scholar
  22. Branko Grünbaum and Geoffrey C Shephard. Pick’s theorem. The American Mathematical Monthly, 100(2):150-161, 1993. Google Scholar
  23. Dorit S Hochbaum. Complexity and approximations for submodular minimization problems on two variables per inequality constraints. Discrete Applied Mathematics, 250:252-261, 2018. Google Scholar
  24. Rajasekhar Inkulu and Sanjiv Kapoor. A polynomial time algorithm for finding an approximate shortest path amid weighted regions. Preprint, 2015. Google Scholar
  25. Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the complexity of minimum-link path problems. JoCG, 8(2):80-108, 2017. Special Issue on SoCG'16. URL: http://jocg.org/index.php/jocg/article/view/328, URL: https://doi.org/10.20382/jocg.v8i2a5.
  26. Niel Lebeck, Thomas Mølhave, and Pankaj K Agarwal. Computing highly occluded paths on a terrain. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 14-23. ACM, 2013. Google Scholar
  27. Niel Lebeck, Thomas Mølhave, and Pankaj K Agarwal. Computing highly occluded paths using a sparse network. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 3-12. ACM, 2014. Google Scholar
  28. David Lichtenstein. Planar formulae and their uses. SIAM journal on computing, 11(2):329-343, 1982. Google Scholar
  29. Max-Jonathan Luckow and Till Fluschnik. On the computational complexity of length-and neighborhood-constrained path problems. arXiv preprint, 2018. URL: http://arxiv.org/abs/1808.02359.
  30. Madhav V Marathe and SS Ravi. On approximation algorithms for the minimum satisfiability problem. Information Processing Letters, 58(1):23-29, 1996. Google Scholar
  31. J. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles. Alg-ca'92, 8(1):431-459, 1992. Google Scholar
  32. Joseph Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. CGTA, 47(6):651-667, 2014. URL: https://doi.org/10.1016/j.comgeo.2013.12.005.
  33. Joseph SB Mitchell and Christos H Papadimitriou. The weighted region problem: finding shortest paths through a weighted planar subdivision. Journal of the ACM (JACM), 38(1):18-73, 1991. Google Scholar
  34. Joseph O'Rourke. Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York, NY, 1987. Google Scholar
  35. Christos H Papadimitriou. An algorithm for shortest-path motion in three dimensions. Information Processing Letters, 20(5):259-263, 1985. Google Scholar
  36. Alexander Pilz. Planar 3-sat with a clause/variable cycle. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.07476.
  37. Valentin Polishchuk and Leonid Sedov. Gender-aware facility location in multi-gender world. In LIPIcs-Leibniz International Proceedings in Informatics, volume 100. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  38. Yuning Song, Liang Liu, Huadong Ma, Athanasios V Vasilakos, et al. A biology-based algorithm to minimal exposure problem of wireless sensor networks. IEEE Trans. Network and Service Management, 11(3):417-430, 2014. Google Scholar
  39. Subhash Suri. A linear-time algorithm for minimum link paths inside a simple polygon. Computer Vision, Graphics and Image Processing, 35(1):99-110, 1986. Google Scholar
  40. Simon Tippenhauer and Wolfgang Muzler. On planar 3-sat and its variants. Fachbereich Mathematik und Informatik der Freien Universitat Berlin, 2016. Google Scholar
  41. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, 2017. Google Scholar
  42. René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for safe convoy routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018, August 23-24, 2018, Helsinki, Finland, pages 10:1-10:19, 2018. Google Scholar
  43. Giacomino Veltri, Qingfeng Huang, Gang Qu, and Miodrag Potkonjak. Minimal and maximal exposure path algorithms for wireless embedded sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems, pages 40-50. ACM, 2003. Google Scholar
  44. Haitao Wang. Quickest visibility queries in polygonal domains. In Boris Aronov and Matya Katz, editors, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, volume 77 of LIPIcs, pages 61:1-61:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  45. Ron Wein, Jur Van Den Berg, and Dan Halperin. Planning high-quality paths and corridors amidst obstacles. The International Journal of Robotics Research, 27(11-12):1213-1231, 2008. Google Scholar
  46. Ron Wein, Jur Van Den Berg, and Dan Halperin. Planning near-optimal corridors amidst obstacles. In Algorithmic Foundation of Robotics VII, pages 491-506. Springer, 2008. Google Scholar
  47. Ron Wein, Jur P Van den Berg, and Dan Halperin. The visibility-voronoi complex and its applications. Computational Geometry, 36(1):66-87, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact