Finding Sets of Points without Empty Convex 6-Gons

Abstract. Erd?s asked whether every large enough set of points in general position in the plane contains six points that form a convex 6-gon without any points from the set in its interior. In this note we show how a set of 29 points was found that contains no empty convex 6-gon. To this end a fast incremental algorithm for finding such 6-gons was designed and implemented and a heuristic search approach was used to find promising sets. The experiments also led to two observations that might be useful in proving that large sets always contain an empty convex 6-gon.     

Finding Sets of Points without Empty Convex 6-Gons

   Abstract. Erd?s asked whether every large enough set of points in general position in the plane contains six points that form a convex 6-gon without any points from the set in its interior. In this note we show how a set of 29 points was found that contains no empty convex 6-gon. To this end a fast incremental algorithm for finding such 6-gons was designed and implemented and a heuristic search approach was used to find promising sets. The experiments also led to two observations that might be useful in proving that large sets always contain an empty convex 6-gon.     

Perfect Partitions of Convex Sets in the Plane

Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Finding Convex Sets Among Points in the Plane

Let g(n) denote the least value such that any g(n) points in the plane in general position contain the vertices of a convex n -gon. In 1935, Erdős and Szekeres showed that g(n) exists, and they obtained the bounds Chung and Graham have recently improved the upper bound by 1; the first improvement since the original Erdős—Szekeres paper. We show that <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>19n3p405.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 1, 1997, and in revised form June 6, 1997.     

Perfect Partitions of Convex Sets in the Plane

   Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Convex Regions in the Plane and their Domes

We make a detailed study of the relation of a euclidean convexregion C Dome (). The dome is the relative boundary, in theupper halfspace model of hyperbolic space, of the hyperbolicconvex hull of the complement of . The first result is to provethat the nearest point retraction r: Dome () is 2-quasiconformal.The second is to establish precise estimates of the distortionof r near . 2000 Mathematics Subject Classification 30C75,30F40, 30F45, 30F60.     

On Extreme Convex Subsets of the Plane

Let Q be a convex compact set in R2 with a non-empty interior. We denoteby C the family of all non-empty closed convex subsets of Q. The aim of thepaper is to characterize the extreme elements of C.     

Reconstructing Convex Polygons in the Plane from One Directed X-Ray

Gardner [7] proved that with the exception of a simple class of nonparallel wedges, convex polygons in the plane are uniquely determined by one directed X-ray. This paper develops methods for reconstructing convex polygons in the plane from one directed X-ray. We show that nonsmooth points on the boundary of a convex body are located along rays where the derivative of the data have a jump discontinuity. Location of the nonsmooth points divides a convex polygon into a finite set of wedges. We prove uniqueness theorems and give algorithms for reconstructing nonparallel wedges from line integrals along four or more rays. Also, we characterize discrete data sets that are directed X-rays of both parallel and nonparallel wedges. Several examples of reconstructions are included. Received August 16, 1999, and in revised form September 13, 2000. Online publication May 4, 2001.     

Computing Skeletons for Rectilinearly Convex Obstacles in the Rectilinear Plane

Journal of Optimization Theory and Applications - We introduce the concept of an obstacle skeleton, which is a set of line segments inside a polygonal obstacle $$omega $$ that can be used in place...     

Allowable Interval Sequences and Separating Convex Sets in the Plane

In 2005, Goodman and Pollack introduced the concept of an allowable interval sequence, a combinatorial object which encodes properties of a family of pairwise disjoint convex sets in the plane. They, Dhandapani, and Holmsen used this concept to address Tverberg’s (1,k)-separation problem: How many pairwise disjoint compact convex sets in the plane are required to guarantee that one can be separated by a line from k others? (Denote this number by f _k .) A new proof was provided that f ₂=5, a result originally obtained by Tverberg himself, and the application of allowable interval sequences to the case of general k was left as an open problem. Hope and Katchalski, using other methods, proved in 1990 that 3k?1≤f _k ≤12(k?1). In this paper, we apply the method of allowable interval sequences to give an upper bound on f _k of under 7.2(k?1), shrinking the range given by Hope and Katchalski by more than half. For a family of translates we obtain a tighter upper bound of approximately 5.8(k?1).     

Primitive Illumination Systems for Families of Convex Bodies in the Plane

Let F= {C₁,C₂,...,C} be a family of ndisjoint convex bodies in the plane. We say that a set Vof exterior light sources illuminates F, if for every boundary point of any member of Fthere is a point in Vsuch that is visible from ,i.e. the open line segment joining and is disjoint from F. An illumination system Vis called primitive if no proper subset of Villuminates F. Let p_max(F) denote the maximum number of points forming a primitive illumination system for F, and letp_max(n) denote the minimum of F) taken over all families Fconsisting of ndisjoint convex bodies in the plane. The aim of this paper is to investigate the quantities p_max(F) and p_max(n).     

Convex Sets in the Plane with Three of Every Four Meeting

Dedicated to the memory of Paul Erdős Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are sufficient to meet every one of the convex sets. Received October 27, 1999/Revised April 11, 2000 RID="*" ID="*" Supported by grant OTKA-T-029074. RID="†" ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234.     

Plane Sections of Convex Bodies of Maximal Volume

Let K = {K ₀ ,... ,K _k } be a family of convex bodies in R ⁿ , 1≤ k≤ n-1 . We prove, generalizing results from [9], [10], [13], and [14], that there always exists an affine k -dimensional plane A _k (subset, dbl equals) R ⁿ , called a common maximal k-transversal of K , such that, for each i∈ {0,... ,k} and each x∈ R ⁿ , where V _k is the k -dimensional Lebesgue measure in A _k and A _k +x . Given a family K = {K _i } _i=0 ^l of convex bodies in R ⁿ , l < k , the set C _k ( K ) of all common maximal k -transversals of K is not only nonempty but has to be ``large' both from the measure theoretic and the topological point of view. It is shown that C <sub>k</sub> ( K ) cannot be included in a ν -dimensional C <sup>1</sup> submanifold (or more generally in an ( H <sup>ν</sup> , ν) -rectifiable, H <sup>ν</sup> -measurable subset) of the affine Grassmannian AGr <sub>n,k</sub> of all affine k -dimensional planes of R <sup>n</sup> , of O(n+1) -invariant ν -dimensional (Hausdorff) measure less than some positive constant c <sub>n,k,l</sub> , where ν = (k-l)(n-k) . As usual, the ``affine' Grassmannian AGr _n,k is viewed as a subspace of the Grassmannian Gr _n+1,k+1 of all linear (k+1) -dimensional subspaces of R ⁿ⁺¹ . On the topological side we show that there exists a nonzero cohomology class θ∈ H ^n-k (G _n+1,k+1 ;Z ₂ ) such that the class θ ^l+1 is concentrated in an arbitrarily small neighborhood of C _k ( K ) . As an immediate consequence we deduce that the Lyusternik—Shnirel'man category of the space C _k ( K ) relative to Gr _n+1,k+1 is ≥ k-l . Finally, we show that there exists a link between these two results by showing that a cohomologically ``big' subspace of Gr _n+1,k+1 has to be large also in a measure theoretic sense. Received May 22, 1998, and in revised form March 27, 2000. Online publication September 22, 2000.     

Covering the Plane with Congruent Copies of a Convex Body

It is shown that every plane compact convex set K with an interiorpoint admits a covering of the plane with density smaller thanor equal to 8(23 – 3)/3 = 1.2376043.... For comparison,the thinnest covering of the plane with congruent circles isof density 2 / 27 = 1.209199576.... (see R. Kershner [3]), whichshows that the covering density bound obtained here is closeto the best possible. It is conjectured that the best possibleis 2 / 27. The coverings produced here are of the double-latticekind consisting of translates of K and translates of —K.     

On the Complexity of the Union of Fat Convex Objects in the Plane

We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times. Received April 7, 1998, and in revised form August 24, 1999.     

Forced Oscillations of an Inclined Plane in an Exponentially-stratified Fluid

The linearized initial-value problem is considered when an inclinedplane, bounding a viscous stratified fluid, is set in oscillatorymotion along the line of greatest slope. The asymptotic solutionfor the induced flow is examined for large times, and an instability,caused by the background stratification, is found in the basiclinear velocity field.     

Perimeter, Diameter and Area of Convex Sets in the Hyperbolic Plane

The paper studies the relation between the asymptotic valuesof the ratios area/length (F/L) and diameter/length (D/L) ofa sequence of convex sets expanding over the whole hyperbolicplane. It is known that F/L goes to a value between 0 and 1depending on the shape of the contour. In the paper, it is firstof all seen that D/L has limit value between 0 and 1/2 in strongcontrast with the euclidean situation in which the lower boundis 1/ (D/L = 1/ if and only if the convex set has constant width).Moreover, it is shown that, as the limit of D/L approaches 1/2,the possible limit values of F/L reduce. Examples of all possiblelimits F/L and D/L are given.