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.     

On Geometric Graphs with No Two Edges in Convex Position

A geometric graph is a graph G=G(V,E) drawn in the plane, where its vertex set V is a set of points in general position and its edge set E consists of straight segments whose endpoints belong to V . Two edges of a geometric graph are in convex position if they are disjoint edges of a convex quadrilateral. It is proved here that a geometric graph with n vertices and no edges in convex position contains at most 2n-1 edges. This almost solves a conjecture of Kupitz. The proof relies on a projection method (which may have other applications) and on a simple result of Davenport—Schinzel sequences of order 2. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p399.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received December 18, 1995, and in revised form June 17, 1997.     

The different ways of stabbing disjoint convex sets

We construct a family ofn disjoint convex set in ^d having (n/(d–1)) ^d–1 geometric permutations. As well, we complete the enumeration problem for geometric permutations of families of disjoint translates of a convex set in the plane, settle the case for cubes in ^d , and construct a family ofd+1 translates in ^d admitting (d+1)!/2 geometric permutations.This research was partly supported by NSERC Grants A3062, A5137, and A8761.     

The maximum size of a convex polygon in a restricted set of points in the plane

Assume we havek points in general position in the plane such that the ratio between the maximum distance of any pair of points to the minimum distance of any pair of points is at mostk, for some positive constant. We show that there exist at leastk ^1/4 of these points which are the vertices of a convex polygon, for some positive constant=(). On the other hand, we show that for every fixed>0, ifk>k(), then there is a set ofk points in the plane for which the above ratio is at most 4k, which does not contain a convex polygon of more thank ^1/3+ vertices.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Cutting disjoint disks by straight lines

Fork>0 letf(k) denote the minimum integerf such that, for any family ofk pairwise disjoint congruent disks in the plane, there is a direction such that any line having direction intersects at mostf of the disks. We determine the exact asymptotic behavior off(k) by proving that there are two positive constantsd ₁,d ₂ such thatd ₁k logkf(k)d ₂k logk. This result has been motivated by problems dealing with the separation of convex sets by straight lines.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.