Lower bounds for weak epsilon-nets and stair-convexity

A set N ⊂ ℝ ^d is called a weak ɛ-net (with respect to convex sets) for a finite X ⊂ ℝ ^d if N intersects every convex set C with |X ∩ C| ≥ ɛ|X|. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ ℝ ^d for which every weak 1/r -net has at least Ω(r log ^d−1 r) points; this is the first superlinear lower bound for weak ɛ-nets in a fixed dimension.     

On Grünbaum's Conjecture about Inner Illumination of Convex Bodies

In 1964 Grünbaum conjectured that any primitive set illuminating from within a convex body in E ^d , d ≥ 3 , has at most 2 ^d points. This was confirmed by V. Soltan in 1995 for the case d = 3 . Here we give a negative answer to Grünbaum's conjecture for all d ≥ 4 , by constructing a convex body K ⊂ E ^d with primitive illuminating sets of an arbitrarily large cardinality. Received December 1, 1997, and in revised form January 21, 1999.     

Determining classes of convex bodies by restricted sets of Steiner symmetrizations

In [4] it was shown that a convex body in R ^d (d≥2) is a simplex if and only if each of its Steiner symmetrals has exactly two extreme points outside the corresponding symmetrization space. A natural question arises about restricted sets of symmetrization directions which guarantee this characterization of simplices. Let denote an arbitrary triple of pairwisedistinct great (d-2)-spheres on the unit sphere of R ^d .We shall prove that a convex body K is a simplex if and only if for every direction the corresponding Steiner symmetral of K has the property described above. Weaker conditions characterize additional classes of convex bodies, e.g. (d-2)-fold pyramids over planar, convex 4-gons.     

More Colourful Simplices

We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in ℝ ^d is contained in at least ⌈(d+1)²/2⌉ simplices with one vertex from each set. This improves the known lower bounds for all d≥4.     

A Lower Bound for Weak ɛ -Nets in High Dimension

   Abstract. A finite set N ⊂ R ^d is a weak ε-net for an n -point set X ⊂ R ^d (with respect to convex sets) if it intersects each convex set K with |K ∩ X| ≥ ε n . It is shown that there are point sets X ⊂ R ^d for which every weak ε -net has at least const ⋅

The Projection Median of a Set of Points in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

The projection median of a finite set of points in ℝ² was introduced by Durocher and Kirkpatrick [Computational Geometry: Theory and Applications, Vol. 42 (5), 364–375, 2009]. They proved that the projection median in ℝ² provides a better approximation of the two-dimensional Euclidean median than the center of mass or the rectilinear median, while maintaining a fixed degree of stability. In this paper we study the projection median of a set of points in ℝ ^d for d≥2. Using results from geometric measure theory we show that the d-dimensional projection median provides a (d/π)B(d/2,1/2)-approximation to the d-dimensional Euclidean median, where B(α,β) denotes the Beta function. We also show that the stability of the d-dimensional projection median is at least \frac1(d/p)B(d/2, 1/2)\frac{1}{(d/\pi)B(d/2, 1/2)}, and its breakdown point is 1/2. Based on the stability bound and the breakdown point, we compare the d-dimensional projection median with the rectilinear median and the center of mass, as a candidate for approximating the d-dimensional Euclidean median. For the special case of d=3, our results imply that the three-dimensional projection median is a (3/2)-approximation of the three-dimensional Euclidean median, which settles a conjecture posed by Durocher.     

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.     

On the Bethe-Sommerfeld conjecture for higher-order elliptic operators

 We consider the elliptic operator P(D)+V in ℝ ^d , d≥2 where P(D) is a constant coefficient elliptic pseudo-differential operator of order 2ℓ with a homogeneous convex symbol P(ξ), and V is a real periodic function in L ^∞(ℝ ^d ). We show that the number of gaps in the spectrum of P(D)+V is finite if 4ℓ>d+1. If in addition, V is smooth and the convex hypersurface {ξℝ ^d :P(ξ)=1} has positive Gaussian curvature everywhere, then the number of gaps in the spectrum of P(D)+V is finite, provided 8ℓ>d+3 and 9≥d≥2, or 4ℓ>d−3 and d≥10. Received: 10 October 2001 / Published online: 28 March 2003 Mathematics Subject Classification (1991): 35J10 Research supported in part by NSF Grant DMS-9732894.     

Convex subdivisions with low stabbing numbers

It is shown that for every subdivision of the d-dimensional Euclidean space, d ≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n/log log n)^1/(d−1)) cells. In other words, if a convex subdivision of d-space has the property that any line stabs at most k cells, then the subdivision has at most exp(O(k ^d−1 log k)) cells. This bound is best possible apart from a constant factor. It was previously known only in the case d = 2. Supported in part by NSERC grant RGPIN 35586.     

A criterion for finite lattice coverings

For a centrally symmetric convex and a covering lattice L for K, a lattice polygon P is called a covering polygon, if . We prove that P is a covering polygon, if and only if its boundary bd(P) is covered by (L ∩ P) + K. Further we show that this characterization is false for non-symmetric planar convex bodies and in Euclidean d–space, d ≥ 3, even for the unit ball K = B ^d. This revised version was published online in June 2006 with corrections to the Cover Date.     

Illuminating Spindle Convex Bodies and Minimizing the Volume of Spherical Sets of Constant Width

A subset of the d-dimensional Euclidean space having nonempty interior is called a spindle convex body if it is the intersection of (finitely or infinitely many) congruent d-dimensional closed balls. The spindle convex body is called a “fat” one, if it contains the centers of its generating balls. The core part of this paper is an extension of Schramm’s theorem and its proof on illuminating convex bodies of constant width to the family of “fat” spindle convex bodies. Also, this leads to the spherical analog of the well-known Blaschke–Lebesgue problem.     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Some characterizing properties of the simplex

We shall prove that a convex body in ^d (d2) is a simplex if, and only if, each of its Steiner symmetrals is a convex double cone over the symmetrization space or, equivalently, has exactly two extreme points outside of this hyperplane. In [3] it is shown that every Steiner symmetral of an arbitrary d-simplex is such a double cone, more precisely a bipyramid. Therefore our main aim is to prove that a convex body which is not a simplex has Steiner symmetrals with more than two extreme points not in the symmetrization space. Some equivalent properties of simplices will also be given.     

On general surfaces defined by an almost linear pfaffian

We calculate the integers d such that a general surface X _d in \mathbbP³{\mathbb{P}^{3}} of degree d contains an arithmetically Gorenstein set of points with a linear syzygy matrix of size 2α + 1. This condition is equivalent to X _d being defined by the pfaffian of a skew-symmetric matrix whose entries are linear except possibly a row and a column. We prove that this takes place for all d ≥ α + 1 if α ≤ 10. Conversely, for α ≥ 11, we show that the condition holds if and only if d is contained in the interval [α + 1, 15].     

Reduced bodies in normed planes

We say that a convex body R of a d-dimensional real normed linear space M ^d is reduced, if Δ(P) < Δ(R) for every convex body P ⊂ R different from R. The symbol Δ(C) stands here for the thickness (in the sense of the norm) of a convex body C ⊂ M ^d . We establish a number of properties of reduced bodies in M ². They are consequences of our basic Theorem which describes the situation when the width (in the sense of the norm) of a reduced body R ⊂ M ² is larger than Δ(R) for all directions strictly between two fixed directions and equals Δ(R) for these two directions.     

Infima of superharmonic functions

Let Ω be a Greenian domain in ℝ ^d , d≥2, or—more generally—let Ω be a connected -Brelot space satisfying axiom D, and let u be a numerical function on Ω, , which is locally bounded from below. A short proof yields the following result: The function u is the infimum of its superharmonic majorants if and only if each set {x:u(x)>t}, t∈ℝ, differs from an analytic set only by a polar set and , whenever V is a relatively compact open set in Ω and x∈V.     

The Maximal Number of Geometric Permutations for n Disjoint Translates of a Convex Set in ℝ Is Ω(n)

A geometric permutation induced by a transversal line of a finite family of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. It is known that the maximal number of geometric permutations in families of n disjoint translates of a convex set in ℝ³ is 3. We prove that for d ≥ 3 the maximal number of geometric permutations for such families in ℝ^d is Ω(n).     

Rate of Approximation of Regular Convex Bodies by?Convex Algebraic Level Surfaces

We consider the problem of the approximation of regular convex bodies in ℝ ^d by level surfaces of convex algebraic polynomials. Hammer (in Mathematika 10, 67–71, 1963) verified that any convex body in ℝ ^d can be approximated by a level surface of a convex algebraic polynomial. In Jaen J. Approx. 1, 97–109, 2009 and subsequently in J. Approx. Theory 162, 628–637, 2010 a quantitative version of Hammer’s approximation theorem was given by showing that the order of approximation of convex bodies by convex algebraic level surfaces of degree n is \frac1n\frac{1}{n}. Moreover, it was also shown that whenever the convex body is not regular (that is, there exists a point on its boundary at which the convex body possesses two distinct supporting hyperplanes), then \frac1n\frac{1}{n} is essentially the sharp rate of approximation. This leads to the natural question whether this rate of approximation can be improved further when the convex body is regular. In this paper we shall give an affirmative answer to this question. It turns out that for regular convex bodies a o(1/n) rate of convergence holds. In addition, if the body satisfies the condition of C ²-smoothness the rate of approximation is O(\frac1n²)O(\frac{1}{n^{2}}).     

On lattice points in polyhedral cross-sections

(a) We prove that the convex hull of anyk ^d +1 points of ad-dimensional lattice containsk+1 collinear lattice points. (b) For a convex polyhedron we consider the numbers of its lattice points in consecutive parallel lattice hyperplanes (levels). We prove that if a polyhedron spans no more than 2 ^d−1 levels, then this string of numbers may be arbitrary. On the other hand, we give an example of a string of 2 ^d−1+1 numbers to which no convex polyhedron corresponds inR ^d .     

Two order superconvergence of finite element methods for Sobolev equations

We consider finite element methods applied to a class of Sobolev equations inR ^d(d ≥ 1). Global strong superconvergence, which only requires that partitions are quais-uniform, is investigated for the error between the approximate solution and the Ritz-Sobolev projection of the exact solution. Two order superconvergence results are demonstrated inW ^1,p (Ω) andL _p(Ω) for 2 ≤p < ∞.