Refine
Language
- English (10)
Keywords
- face numbers of polytopes (2)
- Delaunay triangulations (1)
- Elliptic div-grad operators (1)
- anisotropic ellipticity in three dimensions (1)
- lower bound theorem (1)
- mixed Dirichlet-Neumann boundary conditions (1)
- optimal Sobolev regularity (1)
- perfect graphs (1)
- piecewise linear 3D flattening (1)
- split graphs (1)
We provide a number of new construction techniques for cubical complexes and cubical
polytopes, and thus for cubifications (hexahedral mesh generation). As an application we
obtain an instance of a cubical 4-polytope that has a non-orientable dual manifold (a Klein
bottle). This confirms an existence conjecture of Hetyei (1995).
More systematically, we prove that every normal crossing codimension one immersion of
a compact 2-manifold into R3 is PL-equivalent to a dual manifold immersion of a cubical
4-polytope. As an instance we obtain a cubical 4-polytope with a cubation of Boy's surface
as a dual manifold immersion, and with an odd number of facets. Our explicit example has
17 718 vertices and 16 533 facets. Thus we get a parity changing operation for 3-dimensional
cubical complexes (hexa meshes); this solves problems of Eppstein, Thurston, and others.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
We investigate optimal elliptic
regularity (within the scale of Sobolev spaces) of anisotropic
div--grad operators in three dimensions at a multi-material vertex on
the Neumann boundary part of a polyhedral spatial domain. The
gradient of a solution to the corresponding elliptic PDE (in a
neighbourhood of the vertex) is integrable to an index greater than
three.
Durhuus and Jonsson (1995) introduced the class of “locally constructible” (LC) 3-spheres and showed that there are only exponentially-many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity.
We characterize the LC property for d-spheres ("the sphere minus a facet collapses to a (d-2)-complex") and for d-balls. In particular, we link it to the classical notions of collapsibility, shellability and constructibility, and obtain hierarchies of such properties for
simplicial balls and spheres. The main corollaries from this study are: (1.) Not all simplicial 3-spheres are locally constructible. (This solves a problem by Durhuus and Jonsson.)
(2.) There are only exponentially many shellable simplicial 3-spheres with given number of facets. (This answers a question by Kalai.)
(3.) All simplicial constructible 3-balls are collapsible. (This answers a question by Hachimori.)
(4.) Not every collapsible 3-ball collapses onto its boundary minus a facet. (This property appears in papers by Chillingworth and Lickorish.)
Zonotopes With Large 2D Cuts
(2009)
We analyze a remarkable class of centrally symmetric polytopes, the Hansen
polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes
(they all have at least 3^d nonempty faces) and show that the Hanner polytopes
among them (which have exactly 3^d nonempty faces) correspond to threshold
graphs. Our study produces a new family of Hansen polytopes that have only
3^d+16 nonempty faces.