The Mean Perimeter of Some Random Plane Convex Sets Generated by a Brownian Motion

If C ₁ is the convex hull of the curve of a standard Brownian motion in the complex plane watched from 0 to 1, we consider the convex hulls of C ₁ and several rotations of it and compute the mean of the length of their perimeter by elementary calculations. This can be seen geometrically as a study of the exit time by a Brownian motion from certain polytopes having the unit circle as an inscribed one.     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

Polygonal estimation of planar convex-set perimeter from its two projections

This paper deals with the problem of extracting qualitative and quantitative information from few tomographic projections of an object without reconstructing this object. It focuses on the extraction of quantitative information, precisely the border perimeter estimation for a convex set from horizontal and vertical projections. In the case of a multiple reconstruction, lower and upper bounds for the perimeter are established. In the case of a unique reconstruction, we give conditions and a method for constructing an inscribed polygon in a convex set only from the convex-set projections. An inequality on border perimeter is proved when a convex set is included in another one. The convergence of the polygon perimeter, when the number of vertices increases, is established for such polygons.     

Hyperbolic polygons of minimal perimeter with given angles

We prove that, among all convex hyperbolic polygons with given angles, the perimeter is minimized by the unique polygon with an inscribed circle. The proof relies on work of Schlenker (Trans Am Math Soc 359(5): 2155–2189, 2007).     

Rectangles in triangles

We establish necessary and sufficient conditions on the five positive real numbers a, b, c, u, v for a rectangle with sides u, v to fit in a triangle with sides a, b, c, and we note a few curious consequences.     

Affine-inscribed and affine-circumscribed polygons and polytopes

Five theorems on polygons and polytopes inscribed in (or circumscribed about) a convex compact set in the plane or space are proved by topological methods. In particular, it is proved that for every interior point O of a convex compact set in ℝ³, there exists a two-dimensional section through O circumscribed about an affine image of a regular octagon. It is also proved that every compact convex set in ℝ³ (except the cases listed below) is circumscribed about an affine image of a cube-octahedron (the convex hull of the midpoints of the edges of a cube). Possible exceptions are provided by the bodies containing a parallelogram P and contained in a cylinder with directrix P. Bibliography: 29 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 286–298. Translated by B. M. Bekker.     

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

A note on the largest empty rectangle problem

We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog³ n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog² n) algorithm for our problem.The work of the first author was supported by the Academy of Finland and that of the second by the Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.     

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle α(x,Q) of a point x ∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q⊂C is the minimum aperture angle of any x∈C∖Q with respect to Q. We show that for any compact convex set C in the plane and any k>2, there is an inscribed convex k-gon Q⊂C with aperture angle approximation error . This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k>2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most  . This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00763). NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

Affine images of the rhombo-dodecahedron that are circumscribed about a three-dimensional convex body

The main result of the paper is dual to the author's earlier theorem on the affine images of the cube-octahedron (the convex hull of the midpoints of edges of a cube) inscribed in a three-dimensional convex body. The rhombododecahedron is the polyhedron dual to the cube-octahedron. Let us call a convex body in Κ⊂ℝ³ exceptional if it contains a parallelogram P and is contained in a cylinder with directrix P. It is proved that any nonexceptional convex body is inscribed in an affine image of the rhombo-dodecahedron. The author does not know if the assertion is true for all three-dimensional convex bodies. Bibliography: 2 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 246, 1997, pp. 191–195. Translated by N. Yu. Netsvetaev.     

Maintaining the Extent of a Moving Point Set

Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of S . If the points in S move with algebraic motions, these structures process O(n ^2+\eps ) events. We also give constructions showing that Ω(n ² ) combinatorial changes are possible for these extent functions even if each point is moving with constant velocity. We give a similar construction and upper bound for the convex hull, improving known results. Received April 25, 2000, and in revised form September 25, 2000. Online publication May 4, 2001.     

Convex polytopes whose projection bodies and difference sets are polars

In a paper by the author and B. Weissbach it was proved that the projection body and the difference set of ad-simplex (d≥2) are polars. Obviously, ford=2 a convex domain has this property if and only if its difference set is bounded by a so-called Radon curve. A natural question emerges about further classes of convex bodies inR ^d (d≥3) inducing the mentioned polarity. The aim of this paper is to show that a convexd-polytope (d≥3) is a simplex if and only if its projection body and its difference set are polars.     

Lower Bounds on Strip Discrepancy for Nonatomic Colorings

 A method of proof is given for obtaining lower bounds on strip discrepancy when the distributions do not have atoms. Partition the unit square into an chessboard of congruent square pixels, where n is even. Color of the pixels red, and the rest blue. For any convex set A, let be the difference between the amounts of red and blue areas in A. Under a technical local balance condition, we prove there must be a strip S, of width less than , for which , where c is a positive constant, independent of n and the coloring. The proof extends methods discovered by Alexander and further developed by Chazelle, Matoušek, and Sharir. Integral geometric notions figure prominently. (Received 21 September 1998; in final form 21 February 2000)     

On the structure of convex sets with symmetries

Asymmetry of a compact convex body L ì Rⁿ{\mathcal L \subset {\bf R}^n} viewed from an interior point O{\mathcal O} can be measured by considering how far L{\mathcal L} is from its inscribed simplices that contain O{\mathcal O}. This leads to a measure of symmetry s(L, O){\sigma(\mathcal L, \mathcal O)}. The interior of L{\mathcal L} naturally splits into regular and singular sets, where the singular set consists of points O{\mathcal O} with largest possible s(L, O){\sigma(\mathcal L, \mathcal O)}. In general, to calculate the singular set of a compact convex body is difficult. In this paper we determine a large subset of the singular set in centrally symmetric compact convex bodies truncated by hyperplane cuts. As a function of the interior point O{\mathcal O}, s(L, .){\sigma(\mathcal L, .)} is concave on the regular set. It is natural to ask to what extent does concavity of s(L, .){\sigma(\mathcal L, .)} extend to the whole (interior) of L{\mathcal L}. It has been shown earlier that in dimension two, s(L, .){\sigma(\mathcal L, .)} is concave on L{\mathcal L}. In this paper, we show that in dimensions greater than two, for a centrally symmetric compact convex body L{\mathcal L}, s(L, .){\sigma(\mathcal L, .)} is a non-concave function provided that L{\mathcal L} has a codimension one simplicial intersection. This is the case, for example, for the n-dimensional cube, n ≥ 3. This non-concavity result relies on the fact that a centrally symmetric compact convex body has no regular points.     

The limit shape of convex lattice polygons

It is proved here that, asn→∞, almost all convex (1/n)ℤ²-lattice polygons lying in the square [−1, 1]² are very close to a fixed convex set. This research was partially supported by Hungarian Science Foundation Grants 1907 and 1909.     

Polygons inscribed in a closed curve and a three-dimensional convex body

Here are samples of results obtained in the paper. Let γ be a centrally symmetric closed curve in ℝ ⁿ that does not contain its center of symmetry, O. Then γ is circumscribed about a square (with center O), as well as about a rhombus (also with center O) whose vertices split γ into parts of equal length. If n is odd, then there is a centrally symmetric equilateral 2n-link polyline inscribed in γ and lying in a hyperplane. Let K ⊂ ℝ³ be a convex body, and let x ∈ (0; 1). Then K is circumscribed about an affine-regular pentagonal prism P such that the ratio of the lateral edge l of P to the longest chord of K parallel to l is equal to x. Bibliography: 7 titles.     

Differentiable and analytic families of continuous martingales in manifolds with connection

Summary.  We prove that the derivative of a differentiable family X _t (a) of continuous martingales in a manifold M is a martingale in the tangent space for the complete lift of the connection in M, provided that the derivative is bicontinuous in t and a. We consider a filtered probability space (Ω,(ℱ _t )_{0≤ t ≤1}, ℙ) such that all the real martingales have a continuous version, and a manifold M endowed with an analytic connection and such that the complexification of M has strong convex geometry. We prove that, given an analytic family a↦L(a) of random variable with values in M and such that L(0)≡x ₀∈M, there exists an analytic family a↦X(a) of continuous martingales such that X ₁(a)=L(a). For this, we investigate the convexity of the tangent spaces T ^{( n )} M, and we prove that any continuous martingale in any manifold can be uniformly approximated by a discrete martingale up to a stopping time T such that ℙ(T<1) is arbitrarily small. We use this construction of families of martingales in complex analytic manifolds to prove that every ℱ₁-measurable random variable with values in a compact convex set V with convex geometry in a manifold with a C ¹ connection is reachable by a V-valued martingale. Received: 14 March 1996/In revised form: 12 November 1996     

Multivalued perturbations ofm-accretive differential inclusions

Given anm-accretive operatorA in a Banach spaceX and an upper semicontinuous multivalued mapF: [0,a]×X→2 ^X , we consider the initial value problemu′∈−Au+F(t,u) on [0,a],u(0)=x ₀. We concentrate on the case when the semigroup generated by—A is only equicontinuous and obtain existence of integral solutions if, in particular,X* is uniformly convex andF satisfies β(F(t,B))≤k(t)β(B) for all boundedB⊂X wherek∈L ¹([0,a]) and β denotes the Hausdorff-measure of noncompactness. Moreover, we show that the set of all solutions is a compactR _δ-set in this situation. In general, the extra condition onX* is essential as we show by an example in whichX is not uniformly smooth and the set of all solutions is not compact, but it can be omited ifA is single-valued and continuous or—A generates aC _o-semigroup of bounded linear operators. In the simpler case when—A generates a compact semigroup, we give a short proof of existence of solutions, again ifX* is uniformly (or strictly) convex. In this situation we also provide a counter-example in ℝ⁴ in which no integral solution exists. The author gratefully acknowledges financial support by DAAD within the scope of the French-German project PROCOPE.     

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Two convex disks K and L in the plane are said to cross each other if the removal of their intersection causes each disk to fall into disjoint components. Almost all major theorems concerning the covering density of a convex disk were proved only for crossing-free coverings. This includes the classical theorem of L. Fejes Tóth (Acta Sci. Math. Szeged 12/A:62–67, 1950) that uses the maximum area hexagon inscribed in the disk to give a significant lower bound for the covering density of the disk. From the early seventies, all attempts of generalizing this theorem were based on the common belief that crossings in a plane covering by congruent convex disks, being counterproductive for producing low density, are always avoidable. Partial success was achieved not long ago, first for “fat” ellipses (A. Heppes in Discrete Comput. Geom. 29:477–481, 2003) and then for “fat” convex disks (G. Fejes Tóth in Discrete Comput. Geom. 34(1):129–141, 2005), where “fat” means of shape sufficiently close to a circle. A recently constructed example will be presented here, showing that, in general, all such attempts must fail. Three perpendiculars drawn from the center of a regular hexagon to its three nonadjacent sides partition the hexagon into three congruent pentagons. Obviously, the plane can be tiled by such pentagons. But a slight modification produces a (non-tiling) pentagon with an unexpected covering property: every thinnest covering of the plane by congruent copies of the modified pentagon must contain crossing pairs. The example has no bearing on the validity of Fejes Tóth’s bound in general, but it shows that any prospective proof must take into consideration the existence of unavoidable crossings.     

The element number of the convex regular polytopes

Let Σ be a set of n-dimensional polytopes. A set Ω of n-dimensional polytopes is said to be an element set for Σ if each polytope in Σ is the union of a finite number of polytopes in Ω identified along (n − 1)-dimensional faces. In this paper, we consider the n-dimensional polytopes in general, and extend the notion of element sets to higher dimensions. In particular, we will show that in the 4-space, the element number of the six convex regular polychora is at least 2, and in the n-space (n ≥ 5), the element number is 3, unless n + 1 is a square number.