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

Bliss, Adam; Su, Francis Edward

Discrete Comput. Geom. 33, No. 4, 669-686 (2005).

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

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

Keywords:

polytope; simplicial cover; triangulation; dissection

Citations:

Zbl 0862.52005; Zbl 0822.90101; Zbl 0483.52005; Zbl 0489.52006; Zbl 0483.52003