Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

5. fejezet - Krasnosselsky's art gallery theorem

5. fejezet - Krasnosselsky's art gallery theorem

5.1 Krasnosselsky's art gallery theorem

One of the interesting applications of the general version 4.1.2 of Helly's theorem is the art gallery theorem of M. A. Krasnosselsky (1946). The theorem belongs to the basis of art gallery geometry. It formulates acriteria of viewing all the paintings in the gallery without changing position (this is the case of n=2).

Definition Let D be a non-empty subset in the coordinate space of dimension n and consider the points p and q in D. The point q is said to be visible[6] from p if D contains the segment s(p,q). The set D is star-shaped relative to a point p in D if all the points of D are visible from p. The kernel of D is the collection of those points in D with respect to which D is star-shaped.

Theorem 5.1.1 (M. A. Krasnosselsky) Let D be a non-empty compact subset in the coordinate space of dimension n and suppose that D contains at least

n + 1

points. If for every n+1 points in D there exists a point in D from which they are visible then there exists a point in D from which all the points of D are visible, i.e. D is star-shaped.

Proof Let p be a point in D and consider the set of points in D which are visible from p:

B p : = { q D | s ( p , q ) D } .

(5.1)

First of all we prove that the family of conv B(p)'s (as p runs through the points of D) satisfies the conditions in the general version 4.1.2 of Helly's theorem. To prove that they are compact sets it is enough to check that they are closed because

c o n v B p c o n v D ,

where conv D is compact in the sense of theorem 2.2.2. Let q* be the limit of the convergent sequence q(i) from conv B(p). Using Carathéodory's theorem 2.2.1 for each index i we can write that

q i = λ 1 i v 1 i + + λ n + 1 i v n + 1 i ,

(5.2)

where the right hand side involves a convex combination of elements in B(p). The coefficients obviously form bounded sequences and the sequences

v 1 i , , v n + 1 i

(5.3)

are also bounded because they run in the compact set D. Therefore we can choose uniformly labelled convergent subsequences in a successive way. If

λ 1 * , v 1 * , λ 2 * , v 2 * , , λ n + 1 * , v n + 1 * ,

are their limits then

q * = λ 1 * v 1 * + + λ n + 1 * v n + 1 * ,

where the right hand side involves a convex combination of elements from B(p). Indeed,

λ 1 * + + λ n + 1 * = 1   a n d   λ 1 * 0 , , λ n + 1 * 0

are trivial because the members of the corresponding sequences also satisfy these relations. We should also check that the elements v*(1), ..., v*(n+1) are in B(p). Suppose in contrary that v*(1) is not in B(p) which means that the segment s(v*(1), p) contains an element q in the complement of D. But D is compact (especially closed) and, consequently, there is an open ball around q which is disjoint from D.This ball hides the point p from the elements of a neighbourhood around the endpoint v*(1) which contradicts to the fact that v*(1) is a limit of elements which are visible from p. Therefore q* is in conv B(p) showing that it is a closed subset. Moreover, as a closed subset of conv D, the convex hull of B(p) is also compact. Since for every n+1 points in D there exists a point in D from which they are visible, the general version 4.1.2 of Helly's theorem implies the existence of a common point of the convex hulls of sets in 5.1. Let u be one of the common elements, i.e. u is in conv B(p) for any p in D. To complete the proof we should see that u is also in the intersection of sets in 5.1 (without conv - operator) as p runs through the points of D. Suppose, in contrary, that u is not in B(p) (for some p), i.e. the segment s(p,u) contains an element v in the complement of D. The distance

d ( v , D ) : = m i n { d ( v , q ) | q D }

between v and the compact set D must be strictly positive. Let v(0) be the closest point of D to v along the segment s(p,v) and let z in s(v(0),v) be such a point that

d ( v 0 , z ) < d ( v , D ) .

(5.4)

Finally, let z(0) and p(0) be the points where the distance d(s(z,v), D) is attained at:

d ( z 0 , p 0 ) = d ( s ( z , v ) , D ) : = m i n { d ( w , q ) | w s ( z , v ) , q D } .

Figure 33: The proof of Krasnosselsky's theorem.

Since p(0) is the closest point of D to z(0) we have that

d ( z 0 , D ) = d ( z 0 , p 0 ) = d ( s ( z , v ) , D ) d ( z , v 0 ) < d ( v , D )

because of 5.4. This means that z(0) and v are different. On the other hand a simple nearest-point-type argumentation (see e.g. theorem 3.1 or section 7.1) shows that the hyperplane H(0) perpendicular to the segment s(z(0),p(0)) at p(0) separates z(0) and the points in B(p(0)) (the set of points in D which are visible from p(0)). Therefore the convex hull of B(p(0)) (together with the point u) and z(0) are alsoseparated. In terms of the internal angles of the triangle spanned by p(0), z(0) and u

  t h e   a n g l e   a t   p 0 9 0 t h e   a n g l e   a t   z 0 < 9 0 .

Since z(0) and v are different we have a point on

s ( z 0 , v ) s ( z , v )

which is closer to p(0) than z(0). This contradicts to the choice of z(0).