A Constant Bound for Geometric Permutations of Disjoint Unit Balls

Abstract. We prove that a set of n disjoint unit balls in R ^d admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. The constant bound significantly improves upon the Θ (n ^d-1 ) bound for disjoint balls of unrestricted radii.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

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.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Line Transversals to Disjoint Balls

We prove that the set of directions of lines intersecting three disjoint balls in ℝ³ in a given order is a strictly convex subset of . We then generalize this result to n disjoint balls in ℝ ^d . As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Almost Disjoint Triangles in 3-Space

   Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n ^3/2 ) .     

A Note on Binary Plane Partitions

   Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

Lower bounds to helly numbers of line transversals to disjoint congruent balls

A line ℓ is a transversal to a family F of convex objects in ℝ ^d if it intersects every member of F. In this paper we show that for every integer d ⩾ 3 there exists a family of 2d−1 pairwise disjoint unit balls in ℝ ^d with the property that every subfamily of size 2d − 2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957. Crucial to the proof is the notion of a pinned transversal, which means an isolated point in the space of transversals. Here we investigate minimal pinning configurations and construct a family F of 2d−1 disjoint unit balls in ℝ ^d with the following properties: (i) The space of transversals to F is a single point and (ii) the space of transversals to any proper subfamily of F is a connected set with non-empty interior.     

The k Most Frequent Distances in the Plane

   Abstract. A new upper bound is shown for the number of incidences between n points and n families of concentric circles in the plane. As a consequence, it is shown that the number of the k most frequent distances among n points in the plane is f _n (k)=O(n ^1.4571 k ^.6286 ) improving on an earlier bound of Akutsu, Tamaki, and Tokuyama.     

Disjoint minimal graphs

We prove that the number s(n) of disjoint minimal graphs supported on domains in \mathbbRⁿ{\mathbb{R}^{n}} is bounded by e(n + 1)². In the two-dimensional case, we show that s(2) ≤ 3.     

Almost Disjoint Triangles in 3-Space

Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n ^3/2 ) .     

New Bounds on the Katchalski—Lewis Transversal Problem

   Abstract. In 1980 Katchalski and Lewis showed the following: if each three members of a family of disjoint translates in the plane are met by a line, then there exists a line meeting all but at most k members of F, where k is some positive constant independent of the family. They also showed that k can be taken to be less than 603, and conjectured that k=2 is a universal bound for all such families. In 1990 Tverberg improved the upper bound by showing that k≤ 108 holds. We make further improvements on the upper bound of k , showing that k≤ 22 . Finally, we give a construction of a family of disjoint translates of a parallelogram, each three being met by a line, but where any line misses at least four members. This provides a counterexample to the Katchalski—Lewis conjecture.     

The ring lemma in three dimensions

Suppose that n cyclically tangent discs with pairwise disjoint interiors are externally tangent to and surround the unit disc. The sharp ring lemma in two dimensions states that no disc has a radius below c _n (R ²) = (F _2n−3−1)⁻¹—where F _k denotes the kth Fibonacci number—and that the lower bound is attained in essentially unique Apollonian configurations. In this article, generalizations of the ring lemma to three dimensions are discussed, a version of the ring lemma in three dimensions is proved, and a natural generalization of the extremal two-dimensional configuration—thought to be extremal in three dimensions—is given. The sharp three-dimensional ring lemma constant of order n is shown to be bounded from below by the two-dimensional constant of order n − 1.     

On the injectivity of the Pompeiu transform for integral ball means

A uniqueness theorem is proved for functions defined in \mathbb Rⁿ,   n 3 2 {{\mathbb R}^n}, \; {n \geq 2} , with vanishing integrals over the balls of fixed radius and a given majorant of growth. The problem of unimprovability of this theorem is analyzed.     

Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces

   Abstract. We show that n arbitrary circles in the plane can be cut into O(n ^3/2+ɛ ) arcs, for any ɛ>0 , such that any pair of arcs intersects at most once. This improves a recent result of Tamaki and Tokuyama [20]. We use this result to obtain improved upper bounds on the number of incidences between m points and n circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree.     

Nice Point Sets Can Have Nasty Delaunay Triangulations

   Abstract. We consider the complexity of Delaunay triangulations of sets of points in R ³ under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R ³ with spread Δ has complexity Ω(min{ Δ³, nΔ, n² }) and O(min{ Δ⁴, n ² }). For the case

Improving Rogers' Upper Bound for the Density of Unit Ball Packings via Estimating the Surface Area of Voronoi Cells from Below in Euclidean \sl d -Space for All \sl d ≥ \bf 8

   Abstract. The sphere packing problem asks for the densest packing of unit balls in E ^d . This problem has its roots in geometry, number theory and information theory and it is part of Hilbert's 18th problem. One of the most attractive results on the sphere packing problem was proved by Rogers in 1958. It can be phrased as follows. Take a regular d -dimensional simplex of edge length 2 in E ^d and then draw a d -dimensional unit ball around each vertex of the simplex. Let σ _d denote the ratio of the volume of the portion of the simplex covered by balls to the volume of the simplex. Then the volume of any Voronoi cell in a packing of unit balls in E ^d is at least ω _d /σ _d , where ω _d denotes the volume of a d -dimensional unit ball. This has the immediate corollary that the density of any unit ball packing in E ^d is at most σ _d . In 1978 Kabatjanskii and Levenštein improved this bound for large d . In fact, Rogers' bound is the presently known best bound for 4≤ d≤ 42 , and above that the Kabatjanskii—Levenštein bound takes over. In this paper we improve Rogers' upper bound for the density of unit ball packings in Euclidean d -space for all d≥ 8 and improve the Kabatjanskii—Levenštein upper bound in small dimensions. Namely, we show that the volume of any Voronoi cell in a packing of unit balls in E ^d , d≥ 8 , is at least ω _d /

Polya's inequalities, global uniform integrability and the size of plurisubharmonic lemniscates

First we prove a new inequality comparing uniformly the relative volume of a Borel subset with respect to any given complex euclidean ballB⊂C ⁿ with its relative logarithmic capacity inC ⁿ with respect to the same ballB. An analogous comparison inequality for Borel subsets of euclidean balls of any generic real subspace ofC ⁿ is also proved. Then we give several interesting applications of these inequalities. First we obtain sharp uniform estimates on the relative size of plurisubharmonic lemniscates associated to the Lelong class of plurisubharmonic functions of logarithmic singularities at infinity onC ⁿ as well as the Cegrell class of plurisubharmonic functions of bounded Monge-Ampère mass on a hyperconvex domain Ω⊂(C ⁿ . Then we also deduce new results on the global behaviour of both the Lelong class and the Cegrell class of plurisubharmonic functions. This work was partially supported by the programmes PARS MI 07 and AI.MA 180.