DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.24

Geometric Secluded Paths and Planar Satisfiability

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

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.24,
  author =	{Buchin, Kevin and Polishchuk, Valentin and Sedov, Leonid and Voronov, Roman},
  title =	{{Geometric Secluded Paths and Planar Satisfiability}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.24},
  URN =		{urn:nbn:de:0030-drops-121827},
  doi =		{10.4230/LIPIcs.SoCG.2020.24},
  annote =	{Keywords: Visibility, Route planning, Security/privacy, Planar satisfiability}
}

Document

DOI: 10.4230/LIPIcs.FUN.2018.28

Gender-Aware Facility Location in Multi-Gender World

Authors: Valentin Polishchuk and Leonid Sedov

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract

This interdisciplinary (GS and CS) paper starts from considering the problem of locating restrooms or locker rooms in a privacy-preserving way, i.e., so that while following the path to one's room, one cannot peek into another room; the rooms are meant for a multitude of genders, one room per gender. We then proceed to showing that gender inequality (non-uniform treatment of genders by genders) makes the room placement hard. Finally, we delve into specifics of gender definition and consider locating facilities for the genders in a "perfect" way, i.e., so that navigating to the facilities involves only quick binary decisions; on the way, we indicate that there is room for interpretation the facilities under consideration (we outline several possibilities, depending on the application).

Cite as

Valentin Polishchuk and Leonid Sedov. Gender-Aware Facility Location in Multi-Gender World. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{polishchuk_et_al:LIPIcs.FUN.2018.28,
  author =	{Polishchuk, Valentin and Sedov, Leonid},
  title =	{{Gender-Aware Facility Location in Multi-Gender World}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.28},
  URN =		{urn:nbn:de:0030-drops-88191},
  doi =		{10.4230/LIPIcs.FUN.2018.28},
  annote =	{Keywords: visibility, Strahler number, perfect tree, interval graphs, gender studies}
}

Search Results

Documents authored by Sedov, Leonid

Geometric Secluded Paths and Planar Satisfiability

Abstract

Cite as

Gender-Aware Facility Location in Multi-Gender World

Abstract

Cite as

Thanks for your feedback!

Could not send message