Software for exact integration of polynomials over polyhedra

We are interested in the fast computation of the exact value of integrals of polynomial functions over convex polyhedra. We present speed-ups and extensions of the algorithms presented in previous work by some of the authors. We provide a new software implementation and benchmark computations. The computation of integrals of polynomials over polyhedral regions has many applications; here we demonstrate our algorithmic tools solving a challenge from combinatorial voting theory.     

Higher Schläfli Formulas and Applications

The classical Schläfli formula relates the variations of the dihedral angles of a smooth family of polyhedra in a space-form to the variation of the enclosed volume. We give higher analogues of this formula: for each p, we prove a simple formula relating the variation of the volumes of the codimension p faces to the variation of the 'curvature' – the volumes of the duals of the links in the convex case – of codimension p+2 faces. It is valid also for ideal polyhedra, or for polyhedra with some ideal vertices. This extends results of Suárez-Peiró. The proof is through analoguous smooth formulas. Some applications are described.     

Probability calculations under the IAC hypothesis

We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.     

Dual kinematic formulas

We establish kinematic formulas for dual quermassintegrals of star bodies and for chord power integrals of convex bodies by using dual mixed volumes. These formulas are extensions of the fundamental kinematic formula involving quermassintegrals to the cases of dual quermassintegrals and chord power integrals. Applications to geometric probability are considered.

     

Uniform Estimates for Oscillatory Integrals and Volumes with the Varchenko Phase

We obtain uniform estimates for oscillatory integrals and volumes with a perturbed Varchenko phase, which follow from the statements of general theorems (the case of an arbitrary perturbation). The estimates turn out to be nearly exact. We also derive exact estimates by an argument similar to the proofs of general theorems (the case of a partial perturbation).     

SOME DUAL KINEMATIC FORMULAS

In this article, some kinematic formulas for dual quermassintegral of star bodies and for chord power integrals of convex bodies are established by using dual mixed volumes. These formulas are the extensions of the fundamental kinematic formula involving quermassintegral to the case of dual quermassintegral and chord power integrals.     

Study of flexible algorithmically 1-parametric polyhedra and description of a set of rigid embedded polyhedra

Some formulas are given that describe how the lengths of diagonals of algorithmically 1-para-metric polyhedra and their volumes depend on the bending parameter. By way of application, we present flexibility equations and prove the rigidity of an embedded gluing of two suspensions (bipyramids).     

How to find the volume of a solid of revolution——by using the definite integral

<正>You've already learned that area is one of the many applications of definite integral.This means area is an important application in finding the area in the plane(the two dimensional area).This means the application of integrals to the computation of areas in the plane can be extended to the three dimensional solid.We have another important application is computation of certain volumes in space.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

On surface-minimizing polyhedral decompositions

In this paper the surface-minimizing decompositions of a polyhedron into polyhedra of given volumes is studied. Some corollaries are presented as derivatives of the (local) necessary conditions of optimality, and an overview of the cases when an optimal polyhedral decomposition might exist is also given. An exhaustive classification is given for the case when the polyhedron to be decomposed is convex.     

Combinatorial Structure of Schulte’s Chiral Polyhedra

Schulte classified the discrete chiral polyhedra in Euclidean 3-space and showed that they belong to six families. The polyhedra in three of the families have finite faces and the other three families consist of polyhedra with (infinite) helical faces. We show that all the chiral polyhedra with finite faces are combinatorially chiral. However, the chiral polyhedra with helical faces are combinatorially regular. Moreover, any two such polyhedra with helical faces in the same family are isomorphic.     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.     

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.     

The Face Structure and Geometry of Marked Order Polyhedra

We study a class of polyhedra associated to marked posets. Examples of these polyhedra are Gelfand–Tsetlin polytopes and cones, as well as Berenstein–Zelevinsky polytopes—all of which have appeared in the representation theory of semi-simple Lie algebras. The faces of these polyhedra correspond to certain partitions of the underlying poset and we give a combinatorial characterization of these partitions. We specify a class of marked posets that give rise to polyhedra with facets in correspondence to the covering relations of the poset. On the convex geometrical side, we describe the recession cone of the polyhedra, discuss products and give a Minkowski sum decomposition. We briefly discuss intersections with affine subspaces that have also appeared in representation theory and recently in the theory of finite Hilbert space frames.     

A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization

We propose a new approach to the strict separation of convex polyhedra. This approach is based on the construction of the set of normal vectors for the hyperplanes, such that each one strict separates the polyhedra A and B. We prove the necessary and sufficient conditions of strict separability for convex polyhedra in the Euclidean space and present its applications in optimization.     

Solution of polyhedra

The paper is an exposition of the authors talk on the Seminar on Differential Geometry in IMPA in Rio de Janeiro. It presents a short survey of some recent results in the metric theory of polyhedra in 3-space. Namely we emphasize on some applicatons of the theorem which is a vast generalization of the Herons formule for the area of a triangle to volumes of polyhedra.*The author is partially supported by grants of RFBR No. 02-01-00101 and Russian Ministry of Education E02-1.0-43.     

Numerical solutions of the Laplace’s equation

This paper uses the sinc methods to construct a solution of the Laplace’s equation using two solutions of the heat equation. A numerical approximation is obtained with an exponential accuracy. We also present a reliable algorithm of Adomian decomposition method to construct a numerical solution of the Laplace’s equation in the form a rapidly convergence series and not at grid points. Numerical examples are given and comparisons are made to the sinc solution with the Adomian decomposition method. The comparison shows that the Adomian decomposition method is efficient and easy to use.     

Integral geometry of tensor valuations

We prove a complete set of integral geometric formulas of Crofton type (involving integrations over affine Grassmannians) for the Minkowski tensors of convex bodies. Minkowski tensors are the natural tensor valued valuations generalizing the intrinsic volumes (or Minkowski functionals) of convex bodies. By Hadwiger's general integral geometric theorem, the Crofton formulas yield also kinematic formulas for Minkowski tensors. The explicit calculations of integrals over affine Grassmannians require several integral geometric and combinatorial identities. The latter are derived with the help of Zeilberger's algorithm.     

Finite-volume hyperbolic 4-manifolds that share a fundamental polyhedron

It is known that the volume function for hyperbolic manifolds of dimension 3 is finite-to-one. We show that the number of nonhomeomorphic hyperbolic 4-manifolds with the same volume can be made arbitrarily large. This is done by constructing a sequence of finite-sided finite-volume polyhedra with side-pairings that yield manifolds. In fact, we show that arbitrarily many nonhomeomorphic hyperbolic 4-manifolds may share a fundamental polyhedron. As a by-product of our examples, we also show in a constructive way that the set of volumes of hyperbolic 4-manifolds contains the set of even integral multiples of 4π²/3. This is “half” the set of possible values for volumes, which is the integral multiples of 4π²/3 due to the Gauss-Bonnet formula Vol(M) = 4π²/3 · χ(M).     

Translative integral formulae for convex bodies

Translative versions of the principal kinematic formula for quermassintegrals of convex bodies are studied. The translation integral is shown to be a sum of Crofton type integrals of mixed volumes. As corollaries new integral formulas for mixed volumes are obtained. For smooth centrally symmetric bodies the functionals occurring in the principal translative formula are expressed by measures on Grassmannians which are related to the generating measures of the bodies.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday