Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $T$ be a planar triangulation. It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces). I am trying to obtain a similar upper bound for an extension of this problem, as follows.

Now, let $T$ be a three-dimensional triangulation (a tetrahedralization), and let $S$ be a subset of its edges. We say that $S$ strongly guards $T$ if, for every tetrahedron in $T$, one of the six edges of that tetrahedron lies in $S$. Is there a known nontrivial upper bound for the number of edges required to strongly guard all tetrahedra of a tetrahedralization?

Obviously, this problem can be solved via edge-coloring with no monochromatic tetrahedra. Is there any upper bound on the edge chromatic number for three-dimensional triangulations better than $\Delta + 1$? Maybe the assumption that $T$ is a Delaunay triangulation can conduct to a probabilistic bound.

share|cite|improve this question
I clarified the definition of "guard", but I may have it wrong. In the art-gallery literature, an edge in a 2d triangulation usually guards every triangle that contains at least one endpoint of that edge. In particular, this is the definition used in the paper you cite. – Jeffε Oct 26 '12 at 15:28
A few more questions: (1) Do you mean a triangulation of a convex polytope in $R^3$, of an arbitrary genus-zero polyhedron in $R^3$, of an arbitrary polyhedron in $R^3$, of an arbitrary topological ball, or of an arbitrary 3-manifold? [The paper you cite considers only planar triangulations.] (2) Do you want upper bounds in terms of the number of vertices or the number of edges? [Even if you consider only Delaunay triangulations, an $n$-vertex triangulation can have $\Omega(n^2)$ edges.] – Jeffε Oct 26 '12 at 15:32
@JɛffE, your definition of "guard" is exactly what I meant. The word "triangulation" stands for triangulation of a finite point set $X \subset \mathbf{R}^3$ or, equivalently, triangulation of a convex polytope in $\mathbf{R}^3$, as you suggested. – Vicente Helano Oct 27 '12 at 2:17
I am interested in an upper bound in terms of the number of edges. A 3D Delaunay triangulation can have $\Omega(n^2)$ edges in the worst case, but if we consider points distributed uniformly at random inside the 3-ball there will be an expected linear number of them, right? (Higher-dimensional Voronoi diagrams in expected linear time) – Vicente Helano Oct 27 '12 at 2:41
Sure. Moreover, the expected degree of any edge in the Delaunay triangulation of random points is also constant; you can probably find the precise value in Okabe, Boots, Sugihara, and Chiu. So for some explicit constant $c$, the expected number of necessary edge guards is at most $n/c$. But that's kind of boring, isn't it? – Jeffε Oct 27 '12 at 9:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.