Tell me more ×
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.
up vote 5 down vote favorite
1

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|improve this question
1  
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. – JɛffE 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.] – JɛffE 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? – JɛffE Oct 27 '12 at 9:16
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.