×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv