משפט רדון

בגאומטריה, משפט רדון על קבוצות קמורות, שפורסם על ידי יוהאן רדון בשנת 1921, קובע כי כל קבוצה של $d+2$ נקודות ב-$\mathbb {R} ^{d}$ ניתנת לחלוקה (תורת הקבוצות) לשתי קבוצות אשר הקמוֹר שלהן נחתך. נקודה בחיתוך הקמורים נקראת נקודת רדון.

לדוגמה, במקרה של $d=2$, כל קבוצה של ארבע נקודות במישור האוקלידי ניתנת לחלוקה באחת משתי דרכים: קבוצה בעלת שלוש נקודות ונקודון, שם הקמור של הקבוצה בת שלוש הנקודות הוא משולש וקבוצה זו מכילה את הנקודון; לחלופין, שני זוגות נקודות שקמוריהם הם שני קטעים בעלי נקודת חיתוך.

הוכחה

שתי קבוצות של ארבע נקודות במישור (הקודקודים של ריבוע ומשולש שווה-צלעות ומרכזו), המקדמים פותרים את מערכת של שלוש משוואות ליניאריות עבור נקודות אלה, וחלוקת רדון נוצרת על ידי הפרדת הנקודות עם המקדמים החיוביים ונקודות עם מקדמים השליליים.

תהי $X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbb {R} ^{d}$ קבוצה של $d+2$ נקודות כלשהן. קיימת קבוצה של סקלרים (מקדמים) $a_{1},\dots ,a_{d+2}$, שלא כולם אפסים, שפותרים את מערכת המשוואות הליניאריות

$\sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0$

כיוון שיש $d+2$ נעלמים אך רק $d+1$ משוואות (אחת לכל קואורדינטה ומשוואה נוספת הדורשת מסכום המקדמים להיות אפס) ישנן אינסוף פתרונות למשוואה. נקבע פתרון לא מנוון $a_{1},\dots ,a_{d+2}$ (כלומר, יש $a_{i}$ שונה מאפס וניתן להניח בלי הגבלת הכלליות שהוא חיובי). תהי $I\subseteq X$ קבוצת הנקודות עם המקדמים החיוביים, ותהי $J=X\setminus I$ קבוצת הנקודות עם המקדמים השליליים או אפסיים. $I$ ו-$J$ יוצרים את החלוקה הנדרשת של הנקודות לשתי תתי קבוצות עם קמורים נחתכים.

הקמורים של $I$ ו-$J$ חייבים להיחתך, מכיוון ששניהם מכילים את הנקודה

$p=\sum _{i\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{j\in J}{\frac {-a_{j}}{A}}x_{j}$

כאשר

$A=\sum _{i\in I}a_{i}=-\sum _{j\in J}a_{j}$

הצד השמאלי של הנוסחה ל-$p$ מבטא נקודה זו כצירוף קמור של הנקודות ב-$I$, והצד הימני מבטא זאת כצירוף קמור של הנקודות ב-$J$. לכן, $p$ שייך לשני הקמורים ומשלים את ההוכחה.

שיטת הוכחה זו מאפשרת בנייה יעילה של נקודת רדון, בפרק זמן שהוא פולינום במימד, באמצעות שיטת האלימנציה של גאוס או אלגוריתמים יעילים אחרים כדי לפתור את מערכת המשוואות עבור המקדמים.