## Lower bounds for simplicial covers and triangulations of cubes.(English)Zbl 1078.52013

The authors analyse relationships between minimal simplicial covers and minimal triangulations of polytopes. By definition, a simplicial cover of a convex polytope $$P$$ in $$R^d$$ is a collection of simplices such that (i) the vertices of the simplices are vertices of $$P$$ and (ii) the union of the simplices is $$P$$. The covering number $$C(P)$$ is the minimal number of simplices needed for a cover of $$P$$. A triangulation of $$P$$ is defined as a decomposition of $$P$$ into $$d$$-simplices with disjoint interiors such that each pair of simplices intersects in a face common to both or not at all. Triangulations whose simplices are not required to meet face-to-face are called dissections. Triangulations (dissections) whose vertices are required to be vertices of $$P$$ are reffered to as vertex triangulations (vertex dissections).
Let $$D(P)$$, $$T(P)$$, $$D^v(P)$$ , $$T^v(P)$$ denote, respectively, the size of the smallest possible dissection, triangulation, vertex triangulation, vertex dissection of $$P$$. It is almost evident that $$D(P)\leq T(P)\leq T^v(P)$$ and $$D(P)\leq D^v(P)\leq T^v(P)$$. Besides, $$C(P)\leq D^v(P)$$ since any vertex dissection is a simplicial cover.
The authors prove the inequality $$C(P)\leq T(P)$$, which seems to be more non-trivial then the mentioned ones. On the other hand, there are no known relations between $$C$$ and $$D$$ nor between $$T$$ and $$D^v$$. The authors use the discussed inequalities in order to improve lower bounds for covers and triangulations of cubes $$[0,1]^d \subset R^d$$, $$d=4,\dots, 12$$.
References. 1. R. B. Hughes and M. R. Anderson, Discrete Math. 158, No. 1–3, 99–150 (1996; Zbl 0862.52005), 2. R. B. Hughes, Discrete Math. 133, No. 1–3, 123–138 (1994; Zbl 0822.90101), 3. R. W. Cottle, Discrete Math. 40, 25–29 (1982; Zbl 0483.52005), 4. J. F. Sallee, Discrete Appl. Math. 4, 211–215 (1982; Zbl 0489.52006), and 5. Discrete Math. 40, 81–86 (1982; Zbl 0483.52003).

### MSC:

 52C17 Packing and covering in $$n$$ dimensions (aspects of discrete geometry) 52A20 Convex sets in $$n$$ dimensions (including convex hypersurfaces) 52B11 $$n$$-dimensional polytopes 51M20 Polyhedra and polytopes; regular figures, division of spaces

### Keywords:

polytope; simplicial cover; triangulation; dissection
Full Text: