Edge-guarding orthogonal polyhedra

Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried Toussaint, Jorge Urrutia, Giovanni Viglietta

Research output: Contribution to conferencePaper

Abstract

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 [3] that e/12 are sometimes necessary and e/6 always suf- fice. 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.

Original languageEnglish (US)
StatePublished - 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: Aug 10 2011Aug 12 2011

Other

Other23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CountryCanada
CityToronto, ON
Period8/10/118/12/11

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Edge-guarding orthogonal polyhedra'. Together they form a unique fingerprint.

  • Cite this

    Benbernou, N. M., Demaine, E. D., Demaine, M. L., Kurdia, A., O'Rourke, J., Toussaint, G., Urrutia, J., & Viglietta, G. (2011). Edge-guarding orthogonal polyhedra. Paper presented at 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, ON, Canada.