During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke. In chapter 10 (pdf available on the above site), section 10.2.2. he shows a lower bound of $\Omega\left(n^{3/2}\right)$ on the number of guards needed in three-dimensional art gallery guarding. He says (bold marking is by myself):

In fact, we describe in this section a polyhedron constructed by Seidel that has these two properties.

I believe that the construction, as presented in the book, is not fully correct and thus I tried to find the original work by Seidel. Sadly there is no reference in this section and the only reference in the book with Seidel is Constructing Arrangements of Lines and Hyperplanes with Applications by H. Edelsbrunner, J. O’Rourke, and R. Seidel which does not include the construction.

I have looked through Seidels Google Scholar page but there seems to be nothing relevant.

  • Do you have a source or know anything more about this construction?
  • What could be a good and accepted way for me to obtain information? Contacting either of the two?

1 Answer 1


To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else.

In one of his papers, Seidel even refers to O'Rourke's book for a description of his own construction. He writes on top of page 253 of his joint paper with Jim Ruppert: "In his book [9, p. 255] O'Rourke describes n-vertex three-dimensional polyhedra that require $\Omega(n^{3/2})$ guards."

Jim Ruppert, Raimund Seidel: On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete & Computational Geometry 7: 227-253 (1992)

  • $\begingroup$ Thanks for the answer. I had skimmed the paper you mentioned but not noticed the reference.Then the mention in O'Rourke's book seems to be the only one. I'll leave this question open for a day or two; if nothing else appears I will accept this as the answer. $\endgroup$
    – Artemis
    Jan 18, 2017 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.