2 Search Results for "Shermer, Thomas C."

Document
DOI: 10.4230/LIPIcs.ESA.2024.27
Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof

Authors: Ahmad Biniaz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
O'Rourke (1983) proved that every n-vertex polygon, with n ≥ 4, can be guarded by ⌊ n/4⌋ edges or diagonals - a variant of Chvátal’s theorem for sufficiency of ⌊ n/3⌋ vertices. We present a short proof for a somewhat stronger result that allows us to impose some constraints on the guards. We prove that for every given subset V of vertices, the polygon can be guarded by ⌊(n+2|V|)/4⌋ edges or diagonals that include at least one edge or diagonal incident to every vertex of V. This bound is the best achievable given the constraint for V. Our proof is by induction and suggests a simple linear-time algorithm after triangulating the polygon. The sufficiency of ⌊4⌋ guards is a special case of the new result where V is the empty set.
Cite as

Ahmad Biniaz. Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 27:1-27:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biniaz:LIPIcs.ESA.2024.27,
  author =	{Biniaz, Ahmad},
  title =	{{Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{27:1--27:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.27},
  URN =		{urn:nbn:de:0030-drops-210989},
  doi =		{10.4230/LIPIcs.ESA.2024.27},
  annote =	{Keywords: Polygon guarding, Edge guarding, Short proof, Simple algorithm}
}
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 Author
  • 1 Biniaz, Ahmad
  • 1 Bose, Prosenjit
  • 1 Shermer, Thomas C.

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

  • Refine by Keyword
  • 1 Edge guarding
  • 1 Polygon guarding
  • 1 Short proof
  • 1 Simple algorithm
  • 1 beacon attraction
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2024

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