The log-Minkowski measure of asymmetry for convex bodies

In this paper, we introduce a new measure of asymmetry, called log-Minkowski measure of asymmetry for planar convex bodies in terms of the \(L_0\)-mixed volume, and show that triangles are the most asymmetric planar convex bodies in the sense of this measure of asymmetry.     

Sylvester’s Problem for Symmetric Convex Bodies and Related Problems

We consider moments of the normalized volume of a symmetric or nonsymmetric random polytope in a fixed symmetric convex body. We investigate for which bodies these moments are extremized, and calculate exact values in some of the extreme cases. We show that these moments are maximized among planar convex bodies by parallelograms.     

Sylvester’s Problem for Symmetric Convex Bodies and Related Problems

We consider moments of the normalized volume of a symmetric or nonsymmetric random polytope in a fixed symmetric convex body. We investigate for which bodies these moments are extremized, and calculate exact values in some of the extreme cases. We show that these moments are maximized among planar convex bodies by parallelograms.     

A combinatorial analysis of topological dissections

From a topological space remove certain subspaces (cuts), leaving connected components (regions). We develop an enumerative theory for the regions in terms of the cuts, with the aid of a theorem on the Möbius algebra of a subset of a distributive lattice. Armed with this theory we study dissections into cellular faces and dissections in the d-sphere. For example, we generalize known enumerations for arrangements of hyperplanes to convex sets and topological arrangements, enumerations for simple arrangements and the Dehn-Sommerville equations for simple polytopes to dissections with general intersection, and enumerations for arrangements of lines and curves and for plane convex sets to dissections by curves of the 2-sphere and planar domains.     

Trisections of a 3-rotationally symmetric planar convex body minimizing the maximum relative diameter

In this work we study the fencing problem consisting of finding a trisection of a 3-rotationally symmetric planar convex body which minimizes the maximum relative diameter. We prove that an optimal solution is given by the so-called standard trisection. We also determine the optimal set giving the minimum value for this functional and study the corresponding universal lower bound.     

On a normed version of a Rogers–Shephard type problem

A translation body of a convex body is the convex hull of two of its translates intersecting each other. In the 1950s, Rogers and Shephard found the extremal values, over the family of n-dimensional convex bodies, of the maximal volume of the translation bodies of a given convex body. In our paper, we introduce a normed version of this problem, and for the planar case, determine the corresponding quantities for the four types of volumes regularly used in the literature: Busemann, Holmes–Thompson, and Gromov’s mass and mass*. We examine the problem also for higher dimensions, and for centrally symmetric convex bodies.     

A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lovász.     

Measure-Valued Valuations and Mixed Curvature Measures of Convex Bodies

We prove a polynomial expansion for measure-valued functionals which are translation covariant on the set of convex bodies. The coefficients are measures on product spaces. We then apply this construction to the curvature measures of convex bodies and obtain mixed curvature measures for bodies in general relative position. These are used to generalize an integral geometric formula for nonintersecting convex bodies. Finally, we introduce support measures relative to a quite general structuring body B and describe connections between the different types of measures.     

The parallel volume at large distances

In this paper we examine the asymptotic behavior of the parallel volume of planar non-convex bodies as the distance tends to infinity. We show that the difference between the parallel volume of the convex hull of a body and the parallel volume of the body itself tends to 0. This yields a new proof for the fact that a planar body can only have polynomial parallel volume if it is convex. Extensions to Minkowski spaces and random sets are also discussed.     

与平面凸集几何量有关的不等式(英文)

本文研究了平面凸集几何量之间的关系.通过定义新几何量:平面凸集的最大内接正三角形T和最大内接正方形S,分别获得了T(S)的边长、凸集的直径和面积之间的关系式.     

Polyhedral convexity cuts and negative edge extensions

This note shows that convexity cuts defined relative to polyhedral convex sets can utilize negative as well as positive edge extensions under appropriate circumstances, yielding stronger cuts than customarily available. We also show how to partially collapse the polyhedron to further improve these cuts.     

On Banach–Mazur distance between planar convex bodies

Upper estimates of the diameter and the radius of the family of planar convex bodies with respect to the Banach–Mazur distance are obtained. Namely, it is shown that the diameter does not exceed \(\tfrac{19-\sqrt{73}}{4}\approx 2.614\), which improves the previously known bound of 3, and that the radius does not exceed \(\frac{117}{70}\approx 1.671\).     

On the smallest disk containing a planar reduced convex body

A convex body R of Euclidean space E ^d is said to be reduced if every convex body $ P \subset R $ different from R has thickness smaller than the thickness $ \Delta(R) $ of R. We prove that every planar reduced body R is contained in a disk of radius $ {1\over 2}\sqrt 2 \cdot \Delta(R) $. For $ d \geq 3 $, an analogous property is not true because we can construct reduced bodies of thickness 1 and of arbitrarily large diameter.     

On Blaschke's extension of Bonnesen's inequality

W. Blaschke established a Bonnesen-style inequality for the relative inradius and circumradius of a planar convex bodyK with respect to another. We sharpen this inequality by considering the radii of the minimal convex annulus ofK.     

Lift-and-project cuts for convex mixed integer nonlinear programs

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.     

Planar Location Problems with Block Distance and Barriers

This paper considers one facility planar location problems using block distance and assuming barriers to travel. Barriers are defined as generalized convex sets relative to the block distance. The objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. The problem is solved by modifying the barriers to obtain an equivalent problem and by decomposing the feasible region into a polynomial number of convex subsets on which the objective function is convex. It is shown that solving a planar location problem with block distance and barriers requires at most a polynomial amount of additional time over solving the same problem without barriers.     

Successive radii and Minkowski addition

In this paper we study the behavior of the so called successive inner and outer radii with respect to the Minkowski addition of convex bodies, generalizing the well-known cases of the diameter, minimal width, circumradius and inradius. We get?all possible upper and lower bounds for the radii of the sum of two convex bodies in terms of the sum of the corresponding radii.     

Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.