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