The triples of geometric permutations for families of disjoint translates

A line meeting a family of pairwise disjoint convex sets induces two permutations of the sets. This pair of permutations is called a geometric permutation. We characterize the possible triples of geometric permutations for a family of disjoint translates in the plane. Together with earlier studies of geometric permutations this provides a complete characterization of realizable geometric permutations for disjoint translates.     

On the connected components of the space of line transversals to a family of convex sets

Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ³. We prove that each connected component of ℒ can itself be represented as the space of transversals to some finite family of pairwise disjoint compact convex sets. The research of J. E. Goodman was supported in part by NSF Grant DMS91-22065 and by NSA Grant MDA904-92-H-3069. R. Pollack's research was supported in part by NSF Grant CCR91-22103 and by NSA Grant MDA904-92-H-3075. The research of R. Wenger was supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS90-13220.     

On the exact rate of convergence of frequencies of digits in self-similar sets

We study the exact rate of convergence of frequencies of digits of “normal” points of a self-similar set. Our results have applications to metric number theory. One particular application gives the following surprising result: there is an uncountable family of pairwise disjoint and exceptionally big subsets of ?^d that do not obey the law of the iterated logarithm. More precisely, we prove that there is an uncountable family of pairwise disjoint and exceptionally big sets of points x in ?^d—namely, sets with full Hausdorff dimension—for which the rate of convergence of frequencies of digits in the N-adic expansion of x is either significantly faster or significantly slower than the typical rate of convergence predicted by the law of the iterated logarithm.     

Line Transversals to Unit Disks

Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

Geometric permutations and common transversals

The object of this paper is to study how many essentially different common transversals a family of convex sets on the plane can have. In particular, we consider the case where the family consists of pairwise disjoint translates of a single convex set.     

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R d

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in \R ^d , is Θ (n ^d-1 ) . This improves substantially the upper bound of O(n ^2d-2 ) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5]. Received September 21, 1998, and in revised form March 14, 1999.     

Line Transversals to Unit Disks

   Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

The Lifting Model for Reconfiguration

Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plane at another location, without intersecting any other disk. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. We then extend our results for arbitrary disks to systems of pseudodisks, in particular to sets of homothetic copies of a convex object.     

Cutting Glass

Urrutia asked the following question: Given a family of pairwise disjoint compact convex sets on a sheet of glass, is it true that one can always separate from one another a constant fraction of them using edge-to-edge straight-line cuts? We answer this question in the negative, and establish some lower and upper bounds for the number of separable sets. We also consider the special cases when the family consists of intervals, axis-parallel rectangles, ``fat' sets, or ``fat' sets with bounded size. Received April 7, 1999. Online publication May 16, 2000.     

On quasi-amorphous sets

A set is said to be amorphous if it is infinite, but cannot be written as the disjoint union of two infinite sets. The possible structures which an amorphous set can carry were discussed in [5]. Here we study an analogous notion at the next level up, that is to say replacing finite/infinite by countable/uncountable, saying that a set is quasi-amorphous if it is uncountable, but is not the disjoint union of two uncountable sets, and every infinite subset has a countably infinite subset. We use the Fraenkel–Mostowski method to give many examples showing the diverse structures which can arise as quasi-amorphous sets, for instance carrying a projective geometry, or a linear ordering, or both; reconstruction results in the style of [1] are harder to come by in this case. Received: 8 April 1999 / Published online: 3 October 2001     

Almost disjoint large subsets of semigroups

There are several notions of largeness in a semigroup S that originated in topological dynamics. Among these are thick, central, syndetic and piecewise syndetic. Of these, central sets are especially interesting because they are partition regular and are guaranteed to contain substantial combinatorial structure. It is known that in (N,+) any central set may be partitioned into infinitely many pairwise disjoint central sets. We extend this result to a large class of semigroups (including (N,+)) by showing that if S is a semigroup in this class which has cardinality κ then any central set can be partitioned into κ many pairwise disjoint central sets. We also show that for this same class of semigroups, if there exists a collection of μ almost disjoint subsets of any member S, then any central subset of S contains a collection of μ almost disjoint central sets. The same statement applies if “central” is replaced by “thick”; and in the case that the semigroup is left cancellative, “central” may be replaced by “piecewise syndetic”. The situation with respect to syndetic sets is much more restrictive. For example, there does not exist an uncountable collection of almost disjoint syndetic subsets of N. We investigate the extent to which syndetic sets can be split into disjoint syndetic sets.     

Nine convex sets determine a pentagon with convex sets as vertices

It is proved that if ℱ is a family of nine pairwise disjoint compact convex sets in the plane such that no member of ℱ is contained in the convex hull of the union of two other sets of ℱ, then ℱ has a subfamily ℱ′ with five elements such that no member of ℱ′ is contained in the convex hull of the union of the other sets of ℱ′.     

The Katchalski-Lewis Transversal Problem in R<Superscript>n</Superscript>

Let F be a family of disjoint translates of a compact convex set in the plane. In 1980 Katchalski and Lewis showed that there exists a constant k, independent of F, such that if each three members of F are met by a line, then a "large" subfamily G ⊂ F, with |F\G| ≤ k, is met by a line. In this paper we obtain a higher-dimensional analogue containing the Katchalski-Lewis result. Also we give two constructions of families of pairwise disjoint translates of the unit ball in R³ which answer some related questions.     

Equipartitioning by a convex 3-fan

We show that for a given planar convex set K of positive area there exist three pairwise internally disjoint convex sets whose union is K such that they have equal area and equal perimeter.     

Saddle-Point Optimality: A Look Beyond Convexity

The fact that two disjoint convex sets can be separated by a plane has a tremendous impact on optimization theory and its applications. We begin the paper by illustrating this fact in convex and partly convex programming. Then we look beyond convexity and study general nonlinear programs with twice continuously differentiable functions. Using a parametric extension of the Liu-Floudas transformation, we show that every such program can be identified as a relatively simple structurally stable convex model. This means that one can study general nonlinear programs with twice continuously differentiable functions using only linear programming, convex programming, and the inter-relationship between the two. In particular, it follows that globally optimal solutions of such general programs are the limit points of optimal solutions of convex programs.     

Convexly independent sets

A family of pairwise disjoint compact convex sets is called convexly independent, if none of its members is contained in the convex hull of the union of the other members of the family. The main result of the paper gives an upper bound for the maximum cardinalityh(k, n) of a family of mutually disjoint compact convex sets such that any subfamily of at mostk members of is convexly independent, but no subfamily of sizen is.     

A generalization of hadwiger's transversal theorem to intersecting sets

Given an ordered family of compact convex sets in the plane, if every three sets can be intersected by some directed line consistent with the ordering, then there exists a common transversal of the family. This generalizes Hadwiger's Transversal Theorem to families of compact convex sets which are not necessarily pairwise disjoint. If every six sets can be intersected by some directed line consistent with the ordering, then there exists a common transversal which is consistent with the ordering. If the family is pairwise disjoint and every four sets can be intersected by some directed line consistent with the ordering, then there exists a common transversal which is consistent with the ordering.     

Infinite measure preserving transformations with Radon MSJ

We introduce concepts of Radon MSJ and Radon disjointness for infinite Radon measure preserving homeomorphisms of the locally compact Cantor space. We construct an uncountable family of pairwise Radon disjoint infinite Chacon like transformations. Every such transformation is Radon strictly ergodic, totally ergodic, asymmetric (not isomorphic to its inverse), has Radon MSJ and possesses Radon joinings whose ergodic components are not joinings.     

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.     

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).