Lower bounds for simplicial covers and triangulations of cubes (Q2484008): Difference between revisions

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 \textsl{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. \textit{R. B. Hughes} and \textit{M. R. Anderson}, Discrete Math. 158, No. 1--3, 99--150 (1996; Zbl 0862.52005), 2. \textit{R. B. Hughes}, Discrete Math. 133, No. 1--3, 123--138 (1994; Zbl 0822.90101), 3. \textit{R. W. Cottle}, Discrete Math. 40, 25--29 (1982; Zbl 0483.52005), 4. \textit{J. F. Sallee}, Discrete Appl. Math. 4, 211--215 (1982; Zbl 0489.52006), and 5. Discrete Math. 40, 81--86 (1982; Zbl 0483.52003).