##
**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).

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).

Reviewer: Vasyl Gorkaviy (Kharkov)

### 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 |

PDF
BibTeX
XML
Cite

\textit{A. Bliss} and \textit{F. E. Su}, Discrete Comput. Geom. 33, No. 4, 669--686 (2005; Zbl 1078.52013)

### Online Encyclopedia of Integer Sequences:

Number of simplices in minimal decomposition of an n-cube.Lower bounds for minimal number of simplices in a triangulation of the n-dimensional cube (A019503).