Theorems of Helly’s Type for Partially-closed Half-spaces

LIu JIAN-GuO AND GuO QI

(Department of Mathematics,Suzhou University of Science and Technology,Suzhou,Jiangsu,215009)

Communicated by Ji You-qing

1 Introduction

The well-known classical Helly’s Theorem(see[1]),which states that all members in a finite family of convex sets in the Euclidean space Rnhave a common point if arbitrary n+1 members in the family have a common point,is very profound and important in convex geometry and combinatorial geometry.Also it turns out that Helly’s Theorem has various elegant applications in many branches of mathematics(see[2]–[4]).For its importance,Helly’s theorem has gained much attention since it was found.Various kinds of extensions or generalizations of Helly’s Theorem were proved and the corresponding applications were established in the past years(see[5]–[8]).We refer readers to Danzer’s seminal paper[9]for general references.

There are examples showing that the finiteness of the family in Helly’s Theorem cannot be omitted in general.So,among the extensions or generalizations of Helly’s Theorem,one attempt is to find the conditions(for convex sets)under which Helly’s Theorem holds for in finite families.For instance,Helly’s Theorem holds for(not necessarily finite)families of compact convex sets(see[10]and[11]).

Theorems of Helly’s type for half-spaces with particular conditions appear often in many branches of mathematics.For instance,it was shown in[10]that Helly’s Theorem holds for families of closed half-spaces with the condition that the intersection of some finitely many members in the family is compact,from which the existence of center for Borel probabilities is con firmed,and also Theorem 3.1 in[12](see also[13])is in principle a theorem of Helly’s type in analytic form for families of closed half-spaces with another condition.In this paper,we present,under quite weaker conditions,theorems of Helly’s type for(not necessarily finite)families of partially closed half-spaces(see below for definition)in both analytic and geometric forms,along with examples showing that these conditions cannot be omitted in general.

2 Notation and Definitions

We work with the Euclidean space Rnand do not distinguish points and vectors in Rnintentionally.Let Kndenote the family of all convex bodies(i.e.,compact convex sets with nonempty interior)in Rn.For any subset S⊂Rn,conv(S),cone(S),lin(S)denote the convex hull,the convex conical hull and the linear hull of S,respectively.A map T:Rn→ Rmis called affine if

In particular,an affine map f:Rn→ R is called an affine function.It is known that f:Rn→R is affine if and only if

for some unique u∈ Rnand b∈ R,where〈·,·〉denotes the classical inner product.An affine function f(·)= 〈u,·〉+b is called non-trivial(or invertible)if uo,the origin or the zero vector.The set of affine functions on Rnis denoted by aff(Rn).In this paper,affine functions always mean the ones in aff(Rn)unless other mentioned.

For ou ∈ Rnand b∈ R,the set Hu,b:={x ∈ Rn|〈u,x〉=b}is a hyperplane,and the setandare called closed(resp.open)half-spaces with outer and inner normal u respectively.It is trivial thatetc.,where the affine function

Definition 2.1ForL⊂Hu,b,the setis called a partially-closed half-space with outer(resp.inner)normalu.We adoptandas genericsymbols,to denote a partially-closed half-space(without specifiedL).

Clearly,when L=Ø(resp.L=Hu,b),we get back the open half-spaceor(resp.the closed half-spaceHowever,a partially-closed half-space may not even be convex since L may not be.

A familyof partially-closed half-spaces is called compactly-located if there are αi＞ 0,i∈Λ,such that{αi(ui,bi)}i∈Λ⊂ Rn+1is compact(such a concept is suggested by the fact thatfor any α ＞0),and well-located if intwhere “int” denotes the interior.

3 Theorems of Helly’s Type for Half-spaces

In this section,we show theorems of Helly’s type for families of partially-closed half-spaces in both analytic and geometric forms.We call a family{fi|i∈Λ}of invertible affine functions compactly-located(resp.well-located)if the family{{fi≤0}|i∈Λ}is compactly-located(resp.well-located).

The following proposition is in principle a theorem of Helly’s type in analytic form.

Proposition 3.1Let{fi= 〈ui, ·〉+bi}i∈Λbe compactly-located and well-located.Then the following statements are equivalent:

(1)

(2)For eachu ∈ Rn,〈ui,u〉≤ 0for somei∈Λ;

(3)o ∈ ri(conv{ui0,···,uil})for some affinely independentui0,···,uil,1 ≤ l≤ n,where“ri”denotes the relative interior,i.e.,there are positiveαiksuch that

(4)cone{ui0, ···,uil}=lin{ui0, ···,uil}for some affinely independentui0, ···,uil,1≤l≤n.

Remark 3.1i)Proposition 3.1 is an extension of Theorem 3.1 in[12],where{fi|i∈Λ}is assumed to be a finite family and fi∈ {f ∈ aff(Rn)|f(K)=[0,1]}for some convex body K.

ii)The family of closed half-spaces in Proposition 3.1 can be replaced by a family of partially-closed half-spaces(see the following Theorem 3.1).

In order to prove Proposition 3.1,we need the following lemma.

Lemma 3.1Letfi(·)= 〈ui,·〉+bi,i=0,1,···,m,be non-trivial affine functions.Then,for any(um+1,bm+1)∈ cone{(u0,b0),···,(um,bm)},we have

Proof.Ifthen the equality is obvious;ifthen this is just a reformulation of the well-known generalized Farkas lemma(see[14],p.60).

Proof of Proposition 3.1Without loss of generality,we may clearly assume that{(ui,bi)}i∈Λis compact.

(1)⇒(2).LetAssume that there is a u ∈ Rnsuch that〈ui,u〉＞ 0 for each i.Then,by the continuity of〈·,u〉and by the compactness of{ui}i∈Λ⊂ Rnand{bi}i∈Λ⊂ R(for{(ui,bi)}i∈Λ⊂ Rn+1being compact),there exist constants δ＞ 0 and M ＞ 0 such that〈ui,u〉≥ δ,|bi|≤ M for all i and in turn

for all i and λ ＞ 0.Thus,for any λ ＞ δ/M,a contradiction to(1).

(2) ⇒ (3). Consider the linear spaceIf V={o},then by the separation theorem for closed cones(cone{ui}i∈Λis closed since{ui}i∈Λis compact),there is a u ∈ Rnsuch that{ui}i∈Λ⊂ {x| 〈u,x〉＞ 0},which contradicts(2).So dimV≥1.Now,it is easy to see by induction on the dimension of V that V=cone{ui0,···,uis}for some ui0,···,uis(1 ≤ s ≤ n).

Thus,sincewe havewith,αik≥ 0,which leads towhere αi0:=1+＞ 0.We now let l be the smallest positive integer such that

for some ui0,···,uilwith αik＞ 0 and claim that ui0,···,uilare affinely independent.Suppose that ui0,···,uilare not affinely independent.Thenfor some(not all zero) βi0,···,βilwithWithout loss of generality,let

Then

where αik+λβik≥ 0(0≤ k ≤ l−1)and at least one of them is positive,a contradiction to the choice of l.

It follows from(3.1)that

l≤ n clearly since ui0,···,uilare affinely independent.

(3)⇒ (4).Supposethatui0,···,uil,l≤ n,areaffinely independentand o∈ri(conv{ui0,···,uil}),i.e.,with αik＞ 0.Then for each 0≤ k ≤ l,we have

Thus

(4)⇒ (1).Suppose that lin{ui0,···,uil}=cone{ui0,···,uil}with affinely independent ui0,···,uilfor some 1 ≤ l≤ n.Thenwhere αij≥ 0 with at least one αijpositive.Thus,settingby Lemma 3.1 we have

where we used the fact that{fi0≤ 0}{fil+1≤ 0}= Ø since{fil+1≤ 0}⊂ {fi0＞ 0}following from that writingand inf(resp.sup)f(K):=inf(resp.sup)f(x)forx∈Kx∈Kf ∈ aff(Rn),we have intKØ,inf fi0(K)≥ 0,{fi0=supfi0(K)}={fil+1=inf fil+1(K)}and

Therefore,

This completes the proof.

Now,given L⊂{f=0},we denote{f≤L0}:={f＜0}∪L.Notice that{f≤L0}={f＜ 0}when L= Ø,{f≤L0}={f≤ 0}when L={f=0}and{f≤L0}may not be convex since L may not be.Adopting such notation,we have the following extension of Proposition 3.1.

Theorem 3.1Let{fi= 〈ui,·〉+bi}i∈Λbe compactly-located and well-located.Then the following statements are equivalent:

(1)for arbitraryLi⊂ {fi=0},i∈Λ;

(2)For eachu ∈ Rn,〈ui,u〉≤ 0for somei∈Λ;

(3)The origino ∈ ri(conv{ui0,···,uil})for some affinely independentui0, ···,uil,1 ≤ l≤ n,i.e.,there are positiveαiksuch that

(4)cone{ui0,···,uil}=lin{ui0,···,uil}for some affinely independentui0,···,uil,1≤l≤n.

The proof of Theorem 3.1 follows from Proposition 3.1 and the following proposition.

Proposition 3.2Under the conditions in Proposition3.1or Theorem3.1,Øif and only ifand in turn if and only iffor arbitraryLi⊂ {fi=0},i∈Λ.

Proof.Sincefor arbitrary Li⊂{fi=0}, i∈Λ,andimpliestrivially,we need only to show that if

Now,suppose,i.e.,there isWe point out first that,forthere is a δ＞ 0 such that fi(x∗)≥ δ for i∈Λ,which follows from the continuity of fi(x∗)on(ui,bi),the compactness of{(ui,bi)}i∈Λand fi(x∗) ＞ 0 for all i∈Λ(since x∗∈intWe then have,for λ＜0,

which leads to fi((1−λ)x0+λx∗)→ −∞ uniformly for i∈Λ.Thus,there is λ0＜ 0 such that fi((1− λ0)x0+ λ0x∗)＜ 0 for all i∈Λ,i.e.,and soThe proof is completed.

Now,as a consequence of Theorem 3.1,we have the following theorem of Helly’s type for partially-closed half-spaces.For simplicity,we writefor

Theorem 3.2Let familybe compactly-located and well-located,Li⊂ Hiandfor arbitraryi1,i2,···,in+1∈Λ,then wehave

Proof.SupposeThen by the proof of(1)⇒ (3)in Theorem 3.1,there are affinely independent ui0,ui1,···,uiland positive αi0,αi1,···,αil,1 ≤ l≤ n,such thatThus,by the proof of(3)⇒ (1)in Theorem 3.1 again,we have

a contradiction since l≤n.The proof is completed.

4 Further Discussions

In this section,we discuss the conditions appearing in Proposition 3.1,Theorems 3.1 and 3.2.First,we show by example that the“compactly-located”and “well-located”conditions cannot be omitted in general in Proposition 3.1,Theorems 3.1 and 3.2.

Example 4.1In R2,let uθ=(−cosθ,−sinθ),bθ=1,θ∈Λ:=(0,π).Then the familyis well-located but not compactly-located.Now it is easy to see thatfor arbitrary θ0, θ1, ···, θnbutThis example shows that the “compactlylocated”condition cannot be omitted in general in Proposition 3.1,Theorems 3.1 and 3.2.

Example 4.2In R2,let u1=(1,1),u2=(1,−1),u3=(0,−1),b1=b2=b3=0 and fi(·):= 〈ui,·〉+bi,i=1,2,3(observing that the family{f1,f2,f3}is not welllocated since intThen(0,0)∈int(cone{u1,u2,u3})(also cone{u1,u2,u3}=lin{u1,u2,u3}),however,This example shows that,in Theorem 3.1,the“well-located”condition cannot even be replaced by

Next example shows that the“well-located”condition cannot be replaced byin Theorem 3.2 either.

Example 4.3In R2,let u0+=(1,0),u0−=(−1,0),b0+=b0−=0,bi+=bi−=,i=1,2,···,andbi−,i=0,1,2,···.Then it is easy to see that the familyis compactly-located.Also it is easy to check that

and so inti.e.,the family F is not well-located.Now,for arbitrary∈F(where±is specified),

where j=max{j1,j2,j3}.However,since for any(a,b)∈R2,0}for each j with j＞b,we have

At the end,we point out that without the “well-located” condition,the following conclusion still holds.

Theorem 4.1Let{fi= 〈ui,·〉+bi}i∈Λbe a compactly-located family and the statements

(1),(2),(3),(4)be the same as in Theorem3.1.Then,(1)⇒(2)⇔(3)⇔(4).

Proof.The arguments for(1)⇒(2)⇒(3)⇒(4)are exactly the same as those for Theorem 3.1.So we need only to show(4) ⇒ (2).Suppose that cone{ui0,···,uil}=lin{ui0,···,uil}for some affinely independent ui0,···,uil,1 ≤ l≤ n.If there exists u ∈ Rnsuch that〈ui,u〉＞ 0 for all i∈Λ,in particular,〈uik,u〉＞ 0 for 0≤ k≤ l,then,observingfor some α ≥ 0 with at least one α ＞ 0 since lin{u,···,u}=ijij0i0ilcone{ui0,···,uil},we have 〈−ui0,u〉= −〈ui0,u〉＜ 0 anda contradiction.The proof is completed.

Remark 4.1As expected,since a convex body in Rncan be expressed as the intersection of some(closed)half-spaces,the theorems obtained in this paper will play roles in the study for convex bodies.However,we leave this topic to other papers.

References

[1]Helly E.Über mengen konvexer körper mit gemeinschaftlichen punkten.Jahresber.Deutsch.Math.Verein,1923,32:175–176.

[2]Amenta N.Helly-type theorems and generalized linear programming.Discrete Comput.Geom.,1994,12:241–261.

[3]Dyer M.A Class of Convex Programs with Applications to Computational Geometry.Berlin-Heidelberg-New York:ACM,1992:9–15.

[4]Gaubert S,Meunier F.Carathéodory Helly and the others in the max-plus world.Discrete.Comput.Geom,2010,43:648–662.

[5]Ambrus G,Bezdek A,Fodor F.A Helly-type transveral theorem for n-dimensional unit balls.Arch.Math,2006,86:470–480.

[6]Aronov B,Goodman J E,Pollack R,Wenger R.A Helly-type theorem for hyperplane transversals to well-separated convex sets.Discrete Comput.Geom.,2001,25:507–517.

[7]Breen M.A Helly-type theorem for intersections of orthogonally starshaped sets in Rd.Period.Math.Hung.,2014,68:45–53.

[8]Matousek J.A Helly-type theorem for unions of convex sets.Discrete Comput.Geom.,1997,18:1–12.

[9]Danzer L,Grünbaum B,Klee V.Helly’s Theorem and Its Relatives.in:Proc.Sympos.Pure Math.,VII,Providence,RI:Amer.Math.Soc.,1962:101–180.

[10]Barvinok A.A Course in Convexity.Providence,RI:Amer.Math.Soc.,2002:17–24.

[11]Breen M.A Helly-type theorem for countable intersections of starshaped sets.Arch.Math.,2005,84:282–288.

[12]Guo Q,Toth G.Dual mean Minkowski measures of symmetry for convex bodies.Sci.China Math.,2016,59(7):1383–1394.

[13]Yao D,Guo Q.Measures of asymmetry dual to mean Minkowski measures of asymmetry for convex bodies.Comm.Math.Res.,2016,32(3):207–216.

[14]Urruty H,Lemar C.Fundamentals of Convex Analysis.Berlin-Heidelberg-New York:Springer-Verlag,2001:61–65.