Search results for "Polytope"

The polyhedral Hodge number $h^{2,1}$ and vanishing of obstructions

2000

We prove a vanishing theorem for the Hodge number $h^{2,1}$ of projective toric varieties provided by a certain class of polytopes. We explain how this Hodge number also gives information about the deformation theory of the toric Gorenstein singularity derived from the same polytope. In particular, the vanishing theorem for $h^{2,1}$ implies that these deformations are unobstructed.

The Bernstein Basis and its applications in solving geometric constraint systems

2012

International audience; This article reviews the properties of Tensorial Bernstein Basis (TBB) and its usage, with interval analysis, for solving systems of nonlinear, univariate or multivariate equations resulting from geometric constraints. TBB are routinely used in computerized geometry for geometric modelling in CAD-CAM, or in computer graphics. They provide sharp enclosures of polynomials and their derivatives. They are used to reduce domains while preserving roots of polynomial systems, to prove that domains do not contain roots, and to make existence and uniqueness tests. They are compatible with standard preconditioning methods and fit linear program- ming techniques. However, curre…

Convex bodies and convexity on Grassmann cones

1962

The Linear Ordering Polytope

2010

So far we developed a general integer programming approach for solving the LOP. It was based on the canonical IP formulation with equations and 3-dicycle inequalities which was then strengthened by generating mod-k-inequalities as cutting planes. In this chapter we will add further ingredients by looking for problem- specific inequalities. To this end we will study the convex hull of feasible solutions of the LOP: the so-called linear ordering polytope.

Packing a Trunk

2003

We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.

Solution isolation strategies for the Bernstein polytopes-based solver

2013

The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perfo…

On the number of singularities, zero curvature points and vertices of a simple convex space curve

1995

We prove a generalization of the 4 vertex theorem forC3 closed simple convex space curves including singular and zero curvature points.

An upper bound for nonlinear eigenvalues on convex domains by means of the isoperimetric deficit

2010

We prove an upper bound for the first Dirichlet eigenvalue of the p-Laplacian operator on convex domains. The result implies a sharp inequality where, for any convex set, the Faber-Krahn deficit is dominated by the isoperimetric deficit.

Approximate convex hull of affine iterated function system attractors

2012

International audience; In this paper, we present an algorithm to construct an approximate convex hull of the attractors of an affine iterated function system (IFS). We construct a sequence of convex hull approximations for any required precision using the self-similarity property of the attractor in order to optimize calculations. Due to the affine properties of IFS transformations, the number of points considered in the construction is reduced. The time complexity of our algorithm is a linear function of the number of iterations and the number of points in the output convex hull. The number of iterations and the execution time increases logarithmically with increasing accuracy. In additio…

Polyhedral results for a vehicle routing problem

1991

Abstract The Vehicle Routing Problem is a well known, and hard, combinatorial problem, whose polyhedral structure has deserved little attention. In this paper we consider the particular case in which all the demands are equal (since in the general case the associated polytope may be empty). From a known formulation of the problem we obtain the dimension of the corresponding polytope and we study the facetial properties of every inequality in it.