Paper by Erik D. Demaine
- Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried Toussaint, Jorge Urrutia, and Giovanni Viglietta, “Edge-guarding Orthogonal Polyhedra”, in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
We address the question: How many edge guards are
needed to guard an orthogonal polyhedron of e edges,
r of which are reflex? It was previously established 
that e/12 are sometimes necessary and e/6 always suffice.
In contrast to the closed edge guards used for these
bounds, we introduce a new model, open edge guards
(excluding the endpoints of the edge), which we argue
are in some sense more natural in this context. After
quantifying the relationship between closed and open
edge guards, we improve the upper bound to show that,
asymptotically, (11/72)e (open or closed) edge guards
suffice, or, in terms of r, that (7/12)r suffice. Along
the way, we establish tight bounds relating e and r for
orthogonal polyhedra of any genus.
- The paper is 6 pages.
- The paper is available in PDF (771k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 14, 2019 by