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

<p>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: 
<strong>"In his book [9, p. 255] O'Rourke describes n-vertex three-dimensional polyhedra that require $\Omega(n^{3/2})$ guards."</strong></p>

<blockquote>
  <p>Jim Ruppert, Raimund Seidel: On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete &amp; Computational Geometry 7: 227-253 (1992)</p>
</blockquote>

CC BY-SA 3.0
2017-01-18T20:22:06.720Z
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.
Artemis
CC BY-SA 3.0
2017-01-18T20:01:48.470Z
2017-01-18T20:01:48.470Z
Gamow
<p>During my research (writing my master's thesis) I've stumbled across the book <a href="http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html" rel="noreferrer"><em>Art Gallery Theorems and Algorithms</em> by O’Rourke</a>.
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):</p>

<blockquote>
  <p>In fact, we describe in this section a polyhedron <strong>constructed by Seidel</strong> that has these two properties.</p>
</blockquote>

<p>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 <a href="http://epubs.siam.org/doi/abs/10.1137/0215024" rel="noreferrer"><em>Constructing Arrangements of Lines and Hyperplanes with Applications</em> by H. Edelsbrunner, J. O’Rourke, and R. Seidel</a> which does not include the construction.</p>

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

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

<reference-request><computational-geometry><polytope>
Reference needed for lower bound on number of guards in three-dimensional art gallery guarding
Artemis
# Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

(Asked by: username_0 on 2017-01-18)

During my research (writing my master's thesis) I've stumbled across the book [*Art Gallery Theorems and Algorithms* by O’Rourke](http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html).
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](http://epubs.siam.org/doi/abs/10.1137/0215024) 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?

**Tags:** reference-request, computational-geometry, polytope

---

## 1 answers

### Answer by username_1 on 2017-01-18. Score: 2 | Accepted answer

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)

> **Comments:**
> **username_0**: 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.  

---

