Twierdzenie Helly'ego

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Geometrii.
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Twierdzenie Helly'ego

Post autor: xiikzodz »

Na początek kilka zadań:

1. Wykaż, że dowolny płaski wielokąt o obwodzie nieprzekraczającym \(\displaystyle{ 1}\) leży w pewnym kole o promieniu \(\displaystyle{ \frac 14}\).

2. Na płaszczyźnie \(\displaystyle{ \mathbb{R}^2}\) rozważmy prostokąty \(\displaystyle{ \{P_1,\ldots,P_n\}}\) o wzajemnie równoległych parach boków o tej własności, że każde dwa mają niepuste przecięcie. Wykaż, że wówczas wszystkie prostokąty mają punkt wspólny.

3. Na płaszczyźnie ustalmy zbiór wypukły \(\displaystyle{ A}\). Niech zbiory wypukłe \(\displaystyle{ X_1,\ldots,X_n}\) mają tę własność, że dla dowolnych trzech z nich istnieje przesunięcie zbioru \(\displaystyle{ A}\) mające z tymi trzema niepuste przecięcie. Wykaż, że istnieje przesunięcie zbioru \(\displaystyle{ A}\) mające niepuste przecięcie ze wszystkimi \(\displaystyle{ X_i}\).

4. Na płaszczyźnie rozważmy zbiór punktów \(\displaystyle{ p_1,\ldots p_n}\) o tej własności, że każde trzy z nich leżą w pewnym kole o promieniu \(\displaystyle{ r}\). Wykaż, że istnieje koło o promieniu \(\displaystyle{ r}\), w którym leżą wszystkie punkty \(\displaystyle{ p_i}\).

5. Na płaszczyźnie rozważmy zbiór punktów \(\displaystyle{ p_1,\ldots p_n}\) o tej własności, że każde dwa z nich są oddalone o niewięcej niż \(\displaystyle{ 1}\). Wykaż, że wszystkie punkty \(\displaystyle{ p_i}\) leżą w pewnym kole o promieniu \(\displaystyle{ \frac 1{\sqrt 3}}\).

Zadania te łączy to, że można je rozwiązać stosując inne zadanie podobnego typu, wynik zwany twierdzeniem Helly'ego:

Twierdzenie (Eduard Helly, 1923): Niech \(\displaystyle{ X_1,\ldots,X_n}\), \(\displaystyle{ n\ge 3}\) będą wypukłymi zbiorami płaszczyzny o tej własności, że każde trzy z nich mają niepuste przecięcie. Wówczas przecięcie wszystkich \(\displaystyle{ X_i}\) jest niepuste.

Dowód: Postępujemy indukcyjnie. Dla \(\displaystyle{ n=3}\) nie ma czego dowodzić. Dla kroku indukcyjnego rozważmy zbiór \(\displaystyle{ X_1\ldots,X_{n+1}}\) spełniający założenia i przypuśćmy, że dla dowolnego \(\displaystyle{ i\in\{1,\ldots n+1\}}\) zbiór \(\displaystyle{ Y_i=\bigcap_{j\neq i}X_j}\) jest niepusty, znaczy zawiera element, który nazwiemy \(\displaystyle{ v_i}\). Rozważmy teraz punkty \(\displaystyle{ v_1,v_2,v_3,v_4}\). Albo są one wierzchołkami pewnego czworokąta wypukłego, albo jeden z tych punktów, powiedzmy \(\displaystyle{ v_4}\), leży w trójkącie (być może zdegenerowanym) rozpiętym na pozostałych.

W drugim przypadku punkt \(\displaystyle{ v_4}\) leży w przecięciu zbiorów \(\displaystyle{ Y_1,\ldots Y_4}\), zaś w pierwszym punkt wystarczy rozważyć punkt \(\displaystyle{ v}\) przecięcia przekątnych czworokąta \(\displaystyle{ v_1v_2v_3v_4}\), który leży w przecięciu \(\displaystyle{ Y_1,\ldots,Y_4}\), czyli w zbiorze \(\displaystyle{ \bigcap_{j=1}^{n+1}X_j}\). A to jest teza \(\displaystyle{ \square}\).

Przejdźmy do rozwiązań zadań:

2. Na mocy twierdzenia Helly'ego wystarczy pokazać, że dowolne trzy prostokąty mają niepuste przecięcie. Wybieramy osie układu współrzędnych rownoległe do boków prostokątów. Odcinki będące rzutami dowolnych trzech prostokątów na oś OX mają niepuste przecięcie, powiedzmy zawierające punkt \(\displaystyle{ x}\). Podobnie otrzymujemy punkt \(\displaystyle{ y}\) na osi OY.

Obrazek przepadł na ImageShack.

Wówczas punkt \(\displaystyle{ (x,y)}\) leży w przecięciu tych trzech prostokątów i argument zkończony \(\displaystyle{ \square}\).

3. Niech \(\displaystyle{ \sigma(X)}\) oznacza środek ciężkości zbioru \(\displaystyle{ X}\). Dla każdego \(\displaystyle{ i\in\{1,2,\ldots n\}}\) rozważmy zbiór \(\displaystyle{ Y_i}\) taki, że dla każdego przesunięcia \(\displaystyle{ t}\):

\(\displaystyle{ t(A)\cap X_i \Leftrightarrow \sigma(t(A))\in Y_i}\)

Obrazek przepadł na ImageShack.

to znaczy zbiór \(\displaystyle{ Y_i}\) jest zbiorem środków ciężkości przesunięć zbioru \(\displaystyle{ A}\) mających niepuste przecięcie z \(\displaystyle{ X_i}\). Zbiory \(\displaystyle{ Y_i}\) spełniają założenia twierdzenia Helly'ego, wybierzmy więc punkt \(\displaystyle{ v\in\bigcap Y_i}\). Szukane przesunięcie to takie, że punkt \(\displaystyle{ v}\) jest środkiem ciężkości zbioru \(\displaystyle{ A\square}\).

4. Wystarczy w 3. za \(\displaystyle{ A}\) wziąć koło o promieniu \(\displaystyle{ r\square}\).

5. Na mocy 4. wystarczy wykazać, że każde trzy punkty ze zbioru \(\displaystyle{ \{p_1,\ldots,p_n\}}\) leżą w pewnym kole o promieniu \(\displaystyle{ \frac{1}{\sqrt 3}}\). Wystarczy więc pokazać, że dowolny trójkąt o bokach niedłuższych niż 1 leży w pewnym kole o promieniu \(\displaystyle{ \frac{1}{\sqrt 3}}\). Dla trójkąta rozwartokątnego wystarczy rozważyć koło, którego średnicą jest najdłuższy bok trójkąta, zaś da trójkątów nierozwartokątnych bierzemy koło opisane na trójkącie. Wybieramy parę \(\displaystyle{ a,\alpha}\) - najdłuższy bok trójkąta, kąt naprzeciw tego boku.

Obrazek przepadł na ImageShack.

Wówczas \(\displaystyle{ \alpha\ge\frac\pi 3}\) i z twierdzenia sinusów: \(\displaystyle{ 2R=\frac{a}{\sin\alpha}\le\frac{1}{\sin\frac\pi 3}\le\frac 2{\sqrt 3}}\) \(\displaystyle{ \square}\).

1. Na mocy 4. wystarczy pokazać, że dowolne trzy wierzchołki wielokąta leżą w pewnym kole o promieniu \(\displaystyle{ \frac 14}\). Postępujemy podobnie do 5 \(\displaystyle{ \square}\).

Twierdzenie Helly'ego łatwo uogólnić na wyższe wymiary:

Twierdzenie: Niech \(\displaystyle{ X_1,\ldots,X_n}\), \(\displaystyle{ n\ge d+1}\) będą wypukłymi podzbiorami \(\displaystyle{ \mathbb{R}^d}\) o tej własności, że każde \(\displaystyle{ d+1}\) z nich ma niepuste przecięcie. Wówczas przecięcie wszystkich \(\displaystyle{ X_i}\) jest niepuste.

Przydatna definicja: Wieloindeksem (lub n-wieloindeksem) nazwiemy dowolny podzbiór \(\displaystyle{ I\in\{1,\ldots,n\}}\). Wieloindeksy służą często do indeksowania obiektów geometrycznych w kompleksach łańcuchowych.

Oznaczenia:

\(\displaystyle{ \mbox{conv}(A)}\) to najmniejszy zbiór wypukły zawierający \(\displaystyle{ A}\) zwany również otoczką wypukłą zbioru \(\displaystyle{ A}\).

Dla skończonej rodziny zbiorów \(\displaystyle{ A_1,\ldots A_n}\) oraz wieloindeksu \(\displaystyle{ I\subseteq\{1,\ldots,n\}}\) przyjmijmy \(\displaystyle{ A_I=\bigcap_{j\in I} A_j}\).

\(\displaystyle{ [n]=\{1,\ldots, n\}}\). Oznaczenie stosowane w teorii kompleksów symplicjalnych.

Dowód naśladuje przypadek płaski, przy czym rolę układów czteropunktowych przejmują układy \(\displaystyle{ d+2}\) - punktowe, zaś niepustość przecięć takich układów wynika z:

Lemat (Radon): Niech \(\displaystyle{ a_1,\ldots,a_m\in\mathbb{R}^d}\), \(\displaystyle{ m\ge d+2}\). Istnieją wówczas rozłączne podzbiory \(\displaystyle{ I,J}\) zbioru \(\displaystyle{ [m]}\) takie, że

\(\displaystyle{ \mbox{conv}\{a_i:i\in I\}\cap\mbox{conv}\{a_j:j\in J\}\neq\emptyset.}\)\(\displaystyle{ }\)
.

Dowód lematu 2: Niech \(\displaystyle{ (x_i^1,\ldots,x_i^d)}\) będą współrzędnymi punktu \(\displaystyle{ x_i}\).

Układ \(\displaystyle{ d+1}\) równań z \(\displaystyle{ m}\) niewiadomymi \(\displaystyle{ t_i}\) dla \(\displaystyle{ i\in[m]}\):

\(\displaystyle{ \begin{cases}\sum_{i=1}^mt_i=0 \\\\ \sum_{i=1}^mt_ia_i^r\mbox{ dla }r\in[d] \end{cases}}\)

ma niezerowe rozwiązanie \(\displaystyle{ (t_1,\ldots,t_m)}\), bo \(\displaystyle{ m\ge d+2}\). Niech więc:

\(\displaystyle{ I=\{i:t_i>0\}}\)

\(\displaystyle{ J=\{j:t_j<0\}}\).

Zbiory \(\displaystyle{ I,J}\) są niepuste na mocy pierwszego rownania, oczywiście rozłączne oraz po dodaniu pozostałych rownań stronami otrzymujemy:

\(\displaystyle{ \sum_{i\in I}r_ia_i+\sum_{j\in J}r_ja_j=0}\).

Oznaczywszy \(\displaystyle{ s=\sum_{i\in I}r_i=-\sum_{j\in J}r_j}\) otrzymujemy więc:

\(\displaystyle{ \sum_{i\in I}\frac{r_i}sa_i=-\sum_{j\in J}\frac{r_j}sa_j=0}\)

co kończy argument, bo lewa strona to kombinacja wypukła punktów \(\displaystyle{ \{x_i:i\in I\}}\) a prawa to kombinacja wypukła punktów \(\displaystyle{ \{x_j:j\in J\}}\) \(\displaystyle{ \square}\).

W końcu przechodzimy do dowodu twierdzenia: Dla \(\displaystyle{ n=d+1}\) nie ma czego dowodzić. Dalej przez indukcję. Przypuśćmy, że \(\displaystyle{ n\ge n+2}\) i każda \(\displaystyle{ n-1}\) - elementowa rodzina podbiorów zbioru \(\displaystyle{ \{X_1,\ldots,X_n\}}\) ma niepuste przecięcie. Wybierzmy po jednym punkcie \(\displaystyle{ v_i}\) z każdego zbioru \(\displaystyle{ X_{[n]\setminus\{i\}}}\). Na mocy lematu 2 istnieją rozłączne niepuste \(\displaystyle{ I,J\subseteq[n]}\) oraz punkt \(\displaystyle{ z}\) takie, że:

\(\displaystyle{ z\in\mbox{conv}\{v_i:i\in J\}\cap\mbox{conv}\{v_j:j\in J\}\subseteq X_{[n]\setminus I}\cap X_{[n]\setminus J}\subseteq X_{[n]}}\).

Tym samym argument został zamknięty \(\displaystyle{ \square}\).
ODPOWIEDZ