Another Difficult Combinatorial Geometry Problem

A set X in Rd is said to be m-convex , m.$(A!](B 2 , iff for every m
distinct points in X at least one of the line segments determined by
those points lies in X. Ramsey$(A!/(Bs theorem ,in graph theory, implies
that the intersection of two 3-convex sets is 6-convex. For compact
sets this is best possible in R4 . However in R2 the intersection of
two compact , 3-convex sets is 5-convex. This note includes the best
possible results for the , topology dependent, R2 case . The R3
case is the difficult problem of the Subject. These results complement
those of the late H.G. Eggleston on vector sums of Valentine convex
(aka 3-convex) sets.

Over fifty years ago ,Valentine [6] proved that a closed 3-convex set
in the plane is decomposable into a union of 3 or fewer convex sets.
In his concluding remarks he pointed out that the decomposition theory
in R3 needed to be settled. That is still true today. In [7] he
proved several important results about the points of local non-
convexity of a closed 3-convex set. For such closed sets, points of
local non-convexity lie in the kernel of the set and in the planar ,
closed case all points of local non-convexity are limit points of
isolated points of local non-convexity.

Breen [1] produced topology dependent, decomposition theorems for
planar 3-convex sets. The Introduction to [1] includes an explanation
why a closed planar 3-convex set is simply connected.

Eggleston [3] constructed a remarkable compact 3-convex set in R4
which was not the union of finitely many convex sets. I believe that,
at about the same time, Perles of the Hebrew University of
Jerusalem independently produced a similar , but unpublished,
example.

The broad results included in this note were mentioned in passing by
Eggleston [4] including a reference to my 1978 PhD thesis, Calvert
[2]. Eggleston was my great supervisor.

THEOREM Let X1 and X2 both be simply connected planar, 3-convex sets
then X1 $(A!I(B X2 is 5-convex.

PROOF The outline of an elementary proof will follow two lemmas. The
purely combinatorial and well known LEMMA 1 alone can be used to prove
the theorem for several important special cases.

LEMMA 1. The only graph G of order 5 such that neither G nor its
complement contains a triangle is C5 .

PROOF OF LEMMA 1. If some vertex of G has valency greater than or
equal to 3 then clearly G or its complement contains a triangle.
Hence G is C5.

REMARK 1 . An immediate consequence of LEMMA 1 is that if either X1
or X2 of the THEOREM is a union of two convex sets then the result
follows. It is also easy to construct compact sets X1 and X2 with X1
having just one point of local non-convexity and X2 having just two
points of local non-convexity with X1 $(A!I(B X2 not 4-convex see for
example [2] page 48.

LEMMA 2 is also an immediate consequence of LEMMA 1.

LEMMA 2. If x1$(A!-(Bx5 are five points of X1$(A!I(BX2 with none of the
associated line segments lying in X1$(A!I(BX2 , in other words the x i are
5 visually independent points of the intersection, then no three of
the xi are collinear.



PROOF OF THEOREM. The proof now follows easily but tediously from
considering the convex hull of 5 supposedly visually independent
points of the simply connected X1 and X2 . The cases where the
convex hull is a triangle or pentagon are relatively straightforward
whereas the case of a quadrilateral convex hull requires the
consideration of the two cases : where two non-adjacent sides belong
to each Xi or three belong to one Xi .

REMARK 2. It should be noted that my original detailed proof in [2]
used a result of Erdos and Szekeres [5] that $(A!0(Bfrom five points in the
plane of which no three lie on the same straight line it is always
possible to select four points determining a convex quadrilateral$(A!1(B.
However that proof required consideration of the location of the fifth
point outside the convex hull of the other four.

REMARK 3. It is also noteworthy that X1 $(A!I(B X2 may fail to be 5-convex
if just one of the Xi fails to be simply connected. One somewhat
inelegant example of this is included in [2] pages 41and 42, where
both Xi are also unions of three convex sets.

REMARK 4. Let xi 1$(A!\(B i $(A!\(B 5 be five points on the moment curve with
xi = p($(A&A(Bi) where 0 < $(A&A(Bi $(A!\(B 1 and p($(A&A(B) = ($(A&A(B,$(A&A(B2,$(A&A(B3,$(A&A(B4) . As in
[3] it is possible to construct compact X1 and X2 ,3-convex sets
containing the xi with X1$(A!I(BX2 not 5-convex.

REFERENCES

1. M.Breen, Decomposition theorems for 3-convex subsets of the plane,
Pacific. J. Math. 53, (1974), 43-57.
2. D.I.Calvert, Generalisations of convexity, Doctoral Dissertation,
University of London, (1978).
3. H.G.Eggleston, Valentine convexity in n dimensions, Math Proc.
Camb. Phil. Soc., 80 (1976), 223-228.
4. H.G.Eggleston, Vector sums of Valentine convex sets, Math. Proc.
Camb. Phil. Soc., 92 (1982), 17-19.
5. P.Erdos and G.Szekeres, A combinatorial problem in geometry,
Compos. Math. 2 (1935), 463-470.
6. F.A.Valentine, A three point convexity property, Pacific J. Math.
7 (1957), 1227-1235.
7. F.A.Valentine, The intersection of two convex surfaces and
property P3, Proc. Amer. Math. Soc. 9 (1958), 47-54.


.

Relevant Pages

  • Re: the smallest circle that can enclosed a convex hull
    ... The square of the radius is rho /4 - rho is to be maximize. ... compute the maximal in-circle of the polygonal convex hull of a set of points in the plane ... % Now think of it as a set of slack variables, ...
    (comp.soft-sys.matlab)
  • Re: find polygon
    ... perimeter of convex hull but would have some notches that intruded ... In most cases the perimiter of the convex hull isn't a triangle, ... the convex hull and doesn't have any straight edges, ...
    (comp.programming)
  • Generalized convex perimeter of an n-d object
    ... One could define a "convex perimeter" of any bounded set of points S ... in the plane as p_2= the perimeter of the convex hull of S. ... Note that this generalized convex perimeter is a sort of dual to what ...
    (sci.math)
  • Re: convex hull
    ... > hull, then will the convex hull, defined in this manner, of S be convex ... What if S is the three-element set consiting of the vertices of a triangle? ...
    (sci.math)