Paper by Erik D. Demaine

Reference:

MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Joseph O'Rourke, and Frederick Stock, “Super Guarding and Dark Rays in Art Galleries”, in Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), July 31–August 4, 2023, pages 51–61.

BibTeX

@InProceedings{DarkRays_CCCG2023,
  key           = {MIT},
  AUTHOR        = {{MIT CompGeom Group} and Hugo A. Akitaya and Erik D. Demaine and Adam Hesterberg and Anna Lubiw and Jayson Lynch and Joseph O'Rourke and Frederick Stock},
  TITLE         = {Super Guarding and Dark Rays in Art Galleries},
  BOOKTITLE     = {Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023)},
  bookurl       = {https://wadscccg2023.encs.concordia.ca/},
  MONTH         = {July 31--August 4},
  YEAR          = 2023,
  PAGES         = {51--61},

  unrefereed    = 1,
  length        = {11 pages},
  withstudent   = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/ORourkeADHLLS23},
  comments      = {This paper is also available from the <A HREF="https://wadscccg2023.encs.concordia.ca/assets/pdf/CCCG_2023_proc.pdf#page=61">electronic proceedings</A> and as <A HREF="https://arXiv.org/abs/2404.04613">arXiv:2404.04613</A>.},
}

Abstract:

We explore an Art Gallery variant where each point of a polygon must be seen by k guards, and guards cannot see through other guards. Surprisingly, even covering convex polygons under this variant is not straightforward. For example, covering every point in a triangle k = 4 times (a 4-cover) requires 5 guards, and achieving a 10-cover requires 12 guards. Our main result is tight bounds on k-covering a convex polygon of n vertices, for all k and n. The proofs of both upper and lower bounds are nontrivial. We also obtain bounds for simple polygons, leaving tight bounds an open problem.

Comments:

This paper is also available from the electronic proceedings and as arXiv:2404.04613.

Length:

The paper is 11 pages.

Availability:

The paper is available in PDF (3424k).

See information on file formats.

[Google Scholar search]