Generating and Enumerating Digitally Convex Sets of Trees

A set S of vertices in a graph G with vertex set V is digitally convex if for every vertex \(v \in V\), \(N[v] \subseteq N[S]\) implies \(v \in S\). We show that a vertex belongs to at most half of the digitally convex sets of a graph. Moreover, a vertex belongs to exactly half of the digitally convex sets if and only if it is simplicial. An algorithm that generates all digitally convex sets of a tree is described and sharp upper and lower bounds for the number of digitally convex sets of a tree are obtained. A closed formula for the number of digitally convex sets of a path is derived. It is shown how a binary cotree of a cograph can be used to enumerate its digitally convex sets in linear time.     

Integration of combinatorial decompositions in the presence of collinearities

Many results in Combinatorial Integral Geometry are derived by integration of the combinatorial decompositions associated with finite point sets {P _i } given in the plane ?². However, most previous cases of integration of the decompositions in question were carried out for the point sets {P _i } containing no triads of collinear points, where the familiar algorithm sometimes called the “Four indicator formula” can be used. The present paper is to demonstrate that the complete combinatorial algorithm valid for sets {P _i } not subject to the mentioned restriction opens the path to various results, including the field of Stochastic Geometry. In the paper the complete algorithm is applied first in an integration procedure in a study of the perforated convex domains, i.e convex domains containing a finite array of non-overlapping convex holes. The second application is in the study of random colorings of the plane that are Euclidean motions invariant in distribution, basing on the theory of random polygonal windows from the so-called Independent Angles (IA) class. The method is a direct averaging of the complete combinatorial decompositions written for colorings observed in polygonal windows from the IA class. The approach seems to be quite general, but promises to be especially effective for the random coloring generated by random Poisson polygon process governed by the Haar measure on the group of Euclidean motions of the plane, assuming that a point P ∈ ?² is colored J if P is covered by exactly J polygons of the Poisson process. A general theorem clearing the way for Laplace transform treatment of the random colorings induced on line segments is formulated.     

Best proximity points,cyclic Kannan maps and geodesic metric spaces

We introduce the concept of cyclic Kannan orbital C-nonexpansive mappings and obtain the existence of a best proximity point on a pair of bounded, closed and convex subsets of a strictly convex metric space by using the geometric notion of seminormal structure. We also study the structure of minimal sets for cyclic Kannan C-nonexpansive mappings and show that results similar to the celebrated Goebel– Karlovitz lemma for nonexpansive self-mappings can be obtained for cyclic Kannan C-nonexpansive mappings.     

Intersecting Convex Sets by Rays

What is the smallest number τ=τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following:Given any collection \({\mathcal{C}}\) of n pairwise disjoint compact convex sets in d-dimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most \(\frac{dn+1}{d+1}\) members of \({\mathcal{C}}\).There exist collections of n pairwise disjoint (i) equal-length segments or (ii) disks in the Euclidean plane such that from any point there is a ray that meets at least \(\frac{2n}{3}-2\) of them.We also determine the asymptotic behavior of τ(n) when the convex bodies are fat and of roughly equal size.     

On a question by Corson about point-finite coverings

We answer in the affirmative the following question raised by H. H. Corson in 1961: “Is it possible to cover every Banach space X by bounded convex sets with non-empty interior in such a way that no point of X belongs to infinitely many of them?”Actually, we show the way to produce in every Banach space X a bounded convex tiling of order 2, i.e., a covering of X by bounded convex closed sets with non-empty interior (tiles) such that the interiors are pairwise disjoint and no point of X belongs to more than two tiles.     

Tomography models of random convex polygons

Combinatorial integral geometry possesses some results that can be interpreted as belonging to the field of Geometric Tomography. The main purpose of the present paper is to present a case of parallel X-ray approach to tomography of random convex polygons. However, the Introduction reviews briefly some earlier results by the author that refer to reconstruction of (non-random) convex domains by means of a point X-ray. The main tool in treating the parallel X-rays is disintegrated Pleijel identity, or rather, its averaged version, whose derivation is represented in complete detail. The paper singles out a class of random polygons called tomography models, that offer essential advantages for the analysis. The definition of a tomography model is given in terms of stochastic independence. Fortunately, random translation-invariant Poisson processes of lines in IR ² suggest a class of examples. We recall that each such line process is determined by its rose of directions ρ(?). For rather general ρ(?), the number weighted typical polygon in the polygonal partition of the plane generated by the corresponding Poisson line process happens to be a tomography model. For general tomography models, a differential equation is derived for the Laplace transform for parallel X-rays, that rises several interesting computational problems.     

Packing measure of super separated iterated function systems

Let J be the limit set of an iterated function system in \(\mathbb {R}^d\) satisfying the open set condition. It is well known that the h-dimensional packing measure of J is positive and finite when h is given by Hutchinson’s formula. However, it may be hard to find a formula for the h-dimensional packing measure of J. We introduce the super separation condition and use it to reduce the problem of computing the packing measure to checking densities of a finite number of balls around each point in the limit set. We then use this fact to find formulas for the packing measure of a class of Cantor sets in \(\mathbb {R}\), a class of fractals based on regular convex polygons in \(\mathbb {R}^2\), and a class of fractals based on regular simplexes in \(\mathbb {R}^d\) for \(d \ge 3\).     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

New Criteria for the Existence of a Continuous <Emphasis Type="Italic">ε</Emphasis>-Selection

We study sets admitting a continuous selection of near-best approximations and characterize those sets in Banach spaces for which there exists a continuous ε-selection for each ε > 0. The characterization is given in terms of P-cell-likeness and similar properties. In particular, we show that a closed uniqueness set in a uniformly convex space admits a continuous ε-selection for each ε > 0 if and only if it is B-approximately trivial. We also obtain a fixed point theorem.     

Counting Carambolas

We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of n points in the plane. Configurations of interest include convex polygons, star-shaped polygons and monotone paths. We also consider related problems for directed planar straight-line graphs.     

Inner and outer approximation of convex sets using alignment

We show that there exists, for each closed bounded convex set C in the Euclidean plane with nonempty interior, a quadrangle Q having the following two properties. Its sides support C at the vertices of a rectangle r and at least three of the vertices of Q lie on the boundary of a rectangle R that is a dilation of r with ratio 2. We will prove that this implies that quadrangle Q is contained in rectangle R and that, consequently, the inner approximation r of C has an area of at least half the area of the outer approximation Q of C. The proof makes use of alignment or Schüttelung, an operation on convex sets.     

Concave functions,blaschke products,and polygonal mappings

We consider the class Co(p) of all conformal maps of the unit disk onto the exterior of a bounded convex set. We prove that the triangle mappings, i.e., the functions that map the unit disk onto the exterior of a triangle, are among the extreme points of the closed convex hull of Co(p). Moreover, we prove a conjecture on the closed convex hull of Co(p) for all p ∈ (0, 1) which had partially been proved by the authors for some values of p ∈ (0, 1).     

On distinct distances among points in general position and other related problems

A set of points in the plane is said to be in general position if no three of them are collinear and no four of them are cocircular. If a point set determines only distinct vectors, it is called parallelogram free. We show that there exist n-element point sets in the plane in general position, and parallelogram free, that determine only O(n ²/√log n) distinct distances. This answers a question of Erd?s, Hickerson and Pach. We then revisit an old problem of Erd?s: given any n points in the plane (or in d dimensions), how many of them can one select so that the distances which are determined are all distinct? — and provide (make explicit) some new bounds in one and two dimensions. Other related distance problems are also discussed.     

Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

Asymmetry of Convex Bodies of Constant Width

The symmetry of convex bodies of constant width is discussed in this paper. We proved that for any convex body K?? ⁿ of constant width, \(1\leq \mathrm{as}_{\infty}(K)\leq\frac{n+\sqrt{2n(n+1)}}{n+2}\), where as_∞(?) denotes the Minkowski measure of asymmetry for convex bodies. Moreover, the equality holds on the left-hand side precisely iff K is an Euclidean ball and the upper bounds are attainable, in particular, if n=3, the equality holds on the right-hand side if K is a Meissner body.     

Relative symplectic caps, 4-genus and fibered knots

We prove relative versions of the symplectic capping theorem and sufficiency of Giroux’s criterion for Stein fillability and use these to study the 4-genus of knots. More precisely, suppose we have a symplectic 4-manifold X with convex boundary and a symplectic surface Σ in X such that ?Σ is a transverse knot in ?X. In this paper, we prove that there is a closed symplectic 4-manifold Y with a closed symplectic surface S such that (X,Σ) embeds into (Y,S) symplectically. As a consequence we obtain a relative version of the symplectic Thom conjecture. We also prove a relative version of the sufficiency part of Giroux’s criterion for Stein fillability, namely, we show that a fibered knot whose mondoromy is a product of positive Dehn twists bounds a symplectic surface in a Stein filling. We use this to study 4-genus of fibered knots in \(\mathbb {S}^{3} \). Further, we give a criterion for quasipositive fibered knots to be strongly quasipositive.     

On Semi-Finite Hexagons of Order (2, <Emphasis Type="Italic">t</Emphasis>) Containing a Subhexagon

The research in this paper was motivated by one of the most important open problems in the theory of generalized polygons, namely the existence problem for semi–finite thick generalized polygons. We show here that no semi–finite generalized hexagon of order (2, t) can have a subhexagon H of order 2. Such a subhexagon is necessarily isomorphic to the split Cayley generalized hexagon H(2) or its point–line dual H ^D (2). In fact, the employed techniques allow us to prove a stronger result. We show that every near hexagon \({\mathcal{S}}\) of order (2, t) which contains a generalized hexagon H of order 2 as an isometrically embedded subgeometry must be finite. Moreover, if \({H \cong H^{D}}\)(2) then \({\mathcal{S}}\) must also be a generalized hexagon, and consequently isomorphic to either H ^D (2) or the dual twisted triality hexagon T(2, 8).     

Erdős–Szekeres Theorem for Lines

According to the Erd?s–Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd?s–Szekeres theorem.     

On representations of the feasible set in convex optimization

We consider the convex optimization problem \({\min_{\mathbf{x}} \{f(\mathbf{x}): g_j(\mathbf{x})\leq 0, j=1,\ldots,m\}}\) where f is convex, the feasible set \({\mathbf{K}}\) is convex and Slater’s condition holds, but the functions g _j ’s are not necessarily convex. We show that for any representation of \({\mathbf{K}}\) that satisfies a mild nondegeneracy assumption, every minimizer is a Karush-Kuhn-Tucker (KKT) point and conversely every KKT point is a minimizer. That is, the KKT optimality conditions are necessary and sufficient as in convex programming where one assumes that the g _j ’s are convex. So in convex optimization, and as far as one is concerned with KKT points, what really matters is the geometry of \({\mathbf{K}}\) and not so much its representation.     

Finite Sets as Complements of Finite Unions of Convex Sets

Suppose S?? ^d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ? ^d ?S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ? _S . We consider the graph \(\mathcal {G}_{S}\) whose edges are the 2-element edges of ? _S , and we show that, when d=2, for any sufficiently large set S, the chromatic number of \(\mathcal{G}_{S}\) will be large, even though there exist arbitrarily large finite sets S for which \(\mathcal{G}_{S}\) does not contain large cliques.