5 Search Results for "Shermer, Thomas C."

Document
DOI: 10.4230/LIPIcs.WADS.2025.10
On Geodesic Disks Enclosing Many Points

Authors: Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem.
Cite as

Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle. On Geodesic Disks Enclosing Many Points. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.10,
  author =	{Bose, Prosenjit and Esteban, Guillermo and Orden, David and Silveira, Rodrigo I. and Tuttle, Tyler},
  title =	{{On Geodesic Disks Enclosing Many Points}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.10},
  URN =		{urn:nbn:de:0030-drops-242414},
  doi =		{10.4230/LIPIcs.WADS.2025.10},
  annote =	{Keywords: Enclosing disks, Geodesic disks, Bichromatic}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.46
Guarding Offices with Maximum Dispersion

Authors: Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.
Cite as

Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer. Guarding Offices with Maximum Dispersion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.MFCS.2025.46,
  author =	{Fekete, S\'{a}ndor P. and Kobbe, Kai and Krupke, Dominik and Mitchell, Joseph S. B. and Rieck, Christian and Scheffer, Christian},
  title =	{{Guarding Offices with Maximum Dispersion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-241530},
  doi =		{10.4230/LIPIcs.MFCS.2025.46},
  annote =	{Keywords: Dispersive Art Gallery Problem, vertex guards, office-like polygons, orthogonal polygons, polyominoes, NP-completeness, worst-case optimality, dynamic programming, SAT solver}
}
Artifact
Software
DOI: 10.4230/artifacts.23018
RolfSvenning/ContiguousArtGallery

Authors: Rolf Svenning

Abstract
Cite as

Rolf Svenning. RolfSvenning/ContiguousArtGallery (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{github_impl,
   title = {{RolfSvenning/ContiguousArtGallery}}, 
   author = {Svenning, Rolf},
   note = {Software, Independent Research Fund Denmark (DFF), grant 9131- 00113B, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7;origin=https://github.com/RolfSvenning/ContiguousArtGallery;visit=swh:1:snp:24512c962bdc05c9bff737a006e263acf6b13e78;anchor=swh:1:rev:af66971aa2b832e98dcd6b1fcf8eac88d5901b93}{\texttt{swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7}} (visited on 2025-06-20)},
   url = {https://github.com/RolfSvenning/ContiguousArtGallery},
   doi = {10.4230/artifacts.23018},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.20
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Authors: Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.
Cite as

Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.20,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas and Spalding-Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  title =	{{Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.20},
  URN =		{urn:nbn:de:0030-drops-231720},
  doi =		{10.4230/LIPIcs.SoCG.2025.20},
  annote =	{Keywords: Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.13
Gathering by Repulsion

Authors: Prosenjit Bose and Thomas C. Shermer

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider a repulsion actuator located in an n-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an O(n^2) time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an O(n) time algorithm to find a single such actuator location if one exists. We then provide an O(n) time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists.
Cite as

Prosenjit Bose and Thomas C. Shermer. Gathering by Repulsion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.SWAT.2018.13,
  author =	{Bose, Prosenjit and Shermer, Thomas C.},
  title =	{{Gathering by Repulsion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.13},
  URN =		{urn:nbn:de:0030-drops-88397},
  doi =		{10.4230/LIPIcs.SWAT.2018.13},
  annote =	{Keywords: polygon, kernel, beacon attraction}
}
  • Refine by Type
  • 4 Document/PDF
  • 3 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 4 2025
  • 1 2018

  • Refine by Author
  • 2 Bose, Prosenjit
  • 2 Mitchell, Joseph S. B.
  • 2 Svenning, Rolf
  • 1 Biniaz, Ahmad
  • 1 Esteban, Guillermo
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Art Gallery Problem
  • 1 Bichromatic
  • 1 Combinatorics
  • 1 Computational Geometry
  • 1 Discrete Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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