# Strongly edge-guarding a 3d triangulation

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.

-

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ɛﬀE 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ɛﬀE Oct 26 '12 at 15:32
@JɛﬀE, 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
– JɛﬀE Oct 27 '12 at 9:16
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9042631387710571, "perplexity_flag": "head"}