liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Geometric secluded paths and planar satisfiability
Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering. (AEAR)
Institute of Mathematics and Information Technologies, Petrozavodsk State University, Russia.
2020 (English)In: 36th International Symposium on Computational Geometry (SoCG 2020) / [ed] Sergio Cabello and Danny Z. Chen, Dagstuhl, Germany, 2020, Vol. 164, p. 24:1-24:15Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Dagstuhl, Germany, 2020. Vol. 164, p. 24:1-24:15
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-178800DOI: 10.4230/LIPIcs.SoCG.2020.24OAI: oai:DiVA.org:liu-178800DiVA, id: diva2:1589043
Conference
36th International Symposium on Computational Geometry (SoCG 2020), June 22-26, 2020
Available from: 2021-08-30 Created: 2021-08-30 Last updated: 2021-09-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttps://drops.dagstuhl.de/opus/volltexte/2020/12182/

Authority records

Polishchuk, ValentinSedov, Leonid

Search in DiVA

By author/editor
Polishchuk, ValentinSedov, Leonid
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf