Caratheodory's theorem - convex hull

a1020

New member
שלום,
זה המשפט:

המשפט הזה אומר בעצם שבהינתן סט P של n נקודות בR^d, אז כל נקודה בקמור של P ניתן לייצג ע"י convex combination
של תת קבוצה 'P של P בעלת עד d+1 נקודות.

כלומר אם נותנים לי n נקודות בR^2 (במקרה של d=2), אז אם אקח את הקמור שלהן, אז כל נקודה בקמור
אוכל לייצג כconvex combination של לכל היותר 3 נקודות מתוך n הנקודות שיש לי.

יש לי כמה שאלות לגבי המשפט הזה:
1. מה הסיבה שאי אפשר להסתפק בתת קבוצה של לכל היותר d נקודות? למה d+1?
2. אני רוצה לדעת אם אני לא מתבלבל..הכוונה במשפט הזה היא לא שלכל נקודה x בקמור של n הנקודות
יש את אותו סט של עד d+1 נקודות, נכון?
3. בעצם מה הרעיון במשפט הזה? בעקרון כל נקודה בקמור של n הנקודות היא convex combination של n הנקודות.
ה"כוח" שלו כביכול זה שהוא יותר "יעיל" במובן שאם יש לי עכשיו נגיד אלף נקודות בR^3 למשל, אז כל נקודה בקמור שלהן
אני יודע שאוכל לייצג כconvex combination של רק 4 נקודות מתוך האלף?
האמת שאם d > n אז דווקא המשפט לא נראה לי מועיל.
4. התת קבוצה 'P של P, זו תת קבוצה של נקודות שבהכרח שייכות לקמור של P?
5. מישהו יודע אם קיים אלגוריתם שבהינתן נקודה בקמור, מוצא את אותן עד d+1 נקודות שהמשפט מבטיח את קיומן?

תודה
 

הפרבולה1

Active member
1) לנקודה A במרחב R^d יש d דרגות חופש ( המימד של המרחב הוא d לכן צריך d סקלרים כדי ליצג אותה במרחב )
נניח שיש לנו רק d נקודות P1 P2 ..Pd אז צריך לבחור d סקלרים k1 k2 ...kd כדי ליצג אותה באמצעות convex combination :

ZZZ A=k1*p1+k2*p2+...kd*Pd ZZZ

כביכול נראה שיש לנו d דרגות חופש לבחור את אותם d סקלרים, וזה לא נכון כי יש עוד תנאי שאותם סקלרים צריכים לקיים באמצעות convex combination והוא שסכומם שווה ל 1
k1+k2+...kd=1
ולכן יש לנו רק d-1 דרגות חופש ולכן צריך עוד נקודה (P(d+1 ועוד סקלר

2) כן

3) כן, אבל לא כל 4 נקודות יתאימו צריך שהם לא יהיה על אותו מישור ( בהנחה שיש לפחות נקודוה אחרת בקבוצה שהיא מחוץ לאותו מישור ולכן הקמור הוא תלת ממדי)

4) כן
 
למעלה