Refine
Language
- English (21)
Keywords
- discrete differential geometry (2)
- Conformal parameterizations (1)
- Delaunay triangulation (1)
- Dirichlet energy (1)
- Jordan structure (1)
- Laplace operator (1)
- Smith form (1)
- circle patterns (1)
- compound matrix (1)
- discrete analytic functions (1)
- elementary divisors (1)
- generic perturbation (1)
- indefinite inner product (1)
- integer programming (1)
- invariant polynomials (1)
- lexicographic representatives (1)
- matrix pencil (1)
- matrix polynomial (1)
- meshing (1)
- palindromic matrix polynomial (1)
- perturbation analysis (1)
- rank one perturbation (1)
- selfadjoint matrices (1)
- simplicial surfaces (1)
- structured linearization (1)
- symmetry breaking (1)
- texture mapping (1)
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.
Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the
quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each
r
r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of
the threshold numbers τr such that, for all ε > 0,
E [νr (P )] =
1 − o(1)
o(1)
if n(d) ≤ 2(τr −ε)d for all d
if n(d) ≥ 2(τr +ε)d for all d
holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8].
In particular, these results indicate that the high densities often encountered in polyhedral com-
binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of
0/1-polytopes rather than to the special combinatorics of the underlying problems.
It is known that for each combinatorial type of convex 3-dimensional
polyhedra, there is a representative with edges tangent to the unit sphere.
This representative is unique up to projective transformations that fix the unit
sphere. We show that there is a unique representative (up to congruence) with
edges tangent to the unit sphere such that the origin is the barycenter of the
points where the edges touch the sphere.
We introduce a novel method for the construction of discrete conformal mappings from surface meshes of arbitrary topology to the plane. Our approach is based on circle patterns, i.e., arrangements of circles—one for each face—with prescribed intersection angles. Given these angles the circle radii follow as the unique minimizer of a convex energy. The method supports very flexible boundary conditions ranging from free boundaries to control of the boundary shape via prescribed curvatures. Closed meshes of genus zero can be parameterized over the sphere. To parameterize higher genus meshes we introduce cone singularities at designated vertices. The parameter domain is then a piecewise Euclidean surface. Cone singularities can also help to reduce the often very large area distortion of global conformal maps to moderate levels. Our method involves two optimization problems: a quadratic program and the unconstrained minimization of the circle pattern energy. The latter is a convex function of logarithmic radius variables with simple explicit expressions for gradient and Hessian. We demonstrate the versatility and performance of our algorithm with a variety of examples.
We define a discrete Laplace-Beltrami operator for simplicial surfaces. It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the one defined by Pinkall and Polthier (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic and holomorphic functions, discrete mean curvature, and discrete minimal surfaces.
We present a new mathematical approach to metabolic pathway analysis, characterizing a metabolic network by minimal metabolic behaviors and the reversible metabolic space. Our method uses an outer description of the steady state flux cone, based on sets of irreversible reactions. This is different from existing approaches, such as elementary flux modes or extreme pathways, which use an inner description, based on sets of generating vectors. The resulting description of the flux cone is much more compact. By focussing on the reversible and irreversible reactions, our approach provides a different view of the network, which may also lead to new biological insights.
We prove an existence and uniqueness theorem for weighted Delaunay triangulations (with non-intersecting site-circles) with prescribed combinatorial type and circle intersection angles. Such weighted Delaunay triangulations can also be interpreted as hyperbolic polyhedra with vertices beyond the infinite boundary. The proof is based on a variational principle. This extends similar work by Rivin on Delaunay triangulations and ideal polyhedra to weighted Delaunay triangulations and hyperideal polyhedra.
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the
columns. Special cases are packing and partitioning orbitopes, which
arise from restrictions to matrices with at most or exactly one 1-entry
in each row, respectively. The goal of investigating these polytopes is to
gain insight into ways of breaking certain symmetries in integer programs
by adding constraints, e.g., for a well-known formulation of the graph
coloring problem.
We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns
is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining
inequalities. For the cyclic group case, the descriptions turn out to be
totally unimodular, while for the symmetric group case both the description and the proof are more involved. Nevertheless, the associated
separation problem can be solved in linear time also in this case.
Flux coupling analysis is a method to identify blocked and coupled reactions
in a metabolic network at steady state. We present a new approach to
flux coupling analysis, which uses a minimum set of generators of the steady state
flux cone. Our method does not require to reconfigure the network by splitting
reversible reactions into forward and backward reactions.
By distinguishing different types of reactions (irreversible, pseudo-irreversible,
fully reversible), we show that reaction coupling relationships can only hold
between certain reaction types. Based on this mathematical analysis, we propose
a new algorithm for flux coupling analysis.
For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in
the sense of algebraic geometry. Special attention is paid to the perturbation
behavior of the sign characteristic. Typically, under such a perturbation,
for every given eigenvalue, the largest Jordan block of the eigenvalue is
destroyed and (in case the eigenvalue is real) all other Jordan blocks
keep their sign characteristic. The new eigenvalues, i.e., those eigenvalues of
the perturbed matrix that are not eigenvalues of the original matrix,
are typically simple, and in some cases information is provided about their sign
characteristic (if the new eigenvalue is real). The main results are proved by using
the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky
canonical form and on general results concerning rank one perturbations.
Many applications give rise to matrix polynomials whose coefficients have
a kind of reversal symmetry, a structure we call palindromic.
Several properties of scalar palindromic polynomials are derived,
and together with properties of compound matrices, used to
establish the Smith form of regular and singular T-palindromic matrix polynomials,
over arbitrary fields.
The invariant polynomials are shown to
inherit palindromicity,
and their structure is described in detail.
Jordan structures of palindromic matrix polynomials are characterized,
and necessary conditions for the
existence of structured linearizations established.
In the odd degree case, a constructive procedure for building
palindromic linearizations shows that the necessary conditions are sufficient as well.
The Smith form for *-palindromic polynomials is also analyzed. Finally, results for palindromic matrix polynomials over fields of
characteristic two are presented.
The randomized k-number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k-partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k - 1-dimensional Poisson point process.
Our main result is that every n-dimensional polytope can be
described by at most 2n ? 1 polynomial inequalities and, moreover, these
polynomials can explicitly be constructed. For an n-dimensional pointed
polyhedral cone we prove the bound 2n ? 2 and for arbitrary polyhedra we
get a constructible representation by 2n polynomial inequalities.
The use of point sets instead ofmeshes becamemore popular during
the last years. We present a new method for anisotropic fairing of a
point sampled surface using an anisotropic geometric mean curvature
flow. The main advantage of our approach is that the evolution
removes noise from a point set while it detects and enhances geometric
features of the surface such as edges and corners. We derive
a shape operator, principal curvature properties of a point set, and
an anisotropic Laplacian of the surface. This anisotropic Laplacian
reflects curvature properties which can be understood as the point
set analogue of Taubin’s curvature-tensor for polyhedral surfaces.
We combine these discrete tools with techniques from geometric
diffusion and image processing. Several applications demonstrate
the efficiency and accuracy of our method.
We prove that the Random-Edge simplex algorithm requires an
expected number of at most 13n/pd pivot steps on any simple d-polytope with
n vertices. This is the first nontrivial upper bound for general polytopes. We
also describe a refined analysis that potentially yields much better bounds for
specific classes of polytopes. As one application, we show that for combinatorial
d-cubes, the trivial upper bound of 2d on the performance of Random-Edge
can asymptotically be improved by any desired polynomial factor in d.
Revlex-Initial 0/1-Polytopes
(2005)
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)