Forced Convex n -Gons in the Plane

In a seminal paper from 1935, Erdős and Szekeres showed that for each n there exists a least value g(n) such that any subset of g(n) points in the plane in general position must always contain the vertices of a convex n -gon. In particular, they obtained the bounds which have stood unchanged since then. In this paper we remove the +1 from the upper bound for n ≥ 4 . <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>19n3p367.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.     

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.     

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.     

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

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

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.     

Conflict-Free Coloring of Points and Simple Regions in the Plane

We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.     

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.     

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

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.     

The Cross-Section Body, Plane Sections of Convex Bodies and Approximation of Convex Bodies, II

We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, those of sections of convex bodies and of sections of their circumscribed cylinders. For L ^d a convex body, we take n random segments in L and consider their 'Minkowski average' D. For fixed n, the pth moments of V(D) (1 p < ) are minimized, for V (L) fixed, by the ellipsoids. For k = 2 and fixed n, the pth moment of V(D) is maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.     

A Cutting Plane Algorithm for Linear Reverse Convex Programs

In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.     

A Note on Convex Decompositions of a Set of Points in the Plane

For any set P of n points in general position in the plane there is a convex decomposition of P with at most elements. Moreover, any minimal convex decomposition of such a set P has at most elements, where k is the number of points in the boundary of the convex hull of P.Partially supported by Conacyt, MexicoFinal version received: November 10, 2003