מעגלים ונקודות

[srulikbd]

מעגלים ונקודות

Given n > 3 points in the plane, no 3 collinear, show that there is a circle through 3 of the points such that none of the points lies inside the circle.​

 

[ןן גיל ןן]

כיוון?

נבחר 3 נקודות שרדיוס המעגל דרכן מינימלי. על מנת להוכיח שזה עובד, בהינתן משולש ABC חסום במעגל בעל רדיוס R, יש להוכיח שלכל נקודה X בתוך המעגל, לפחות אחד המשולשים ABX, ACX, BCX הינו בעל רדיוס מעגל חוסם קטן מ- R.

 

[עריסטו]

../images/Emo62.gif

נבחר שתי נקודות A ו - C כך שכל שאר הנקודות נמצאות בצד אחד של הישר AC. נבחר נקודה B כך שהזווית ABC מקסימלית. המעגל החוסם את המשולש ABC מתאים לדרישה.

 

[עריסטו]

פתרון נוסף

נבחר שתי נקודות A ו - C כך שהמרחק AC מינימלי. נבחר נקודה B כך שהזווית ABC מקסימלית. אזי הזווית ABC היא זווית חדה (כי מול צלע קטנה במשולש נמצאת זווית קטנה) ולכן המעגל החוסם את המשולש ABC מתאים לדרישה.

 

[טלמון סילבר]

פתרונות נחמדים ../images/Emo45.gif

 

[מספר6]

חידת המשך

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

 

[עריסטו]

מאוד קל להוכיח שהוא מישורי...

מההגדרה נובע שהמעגל החוסם משולש כלשהו אינו מכיל נקודה נוספת, לכן גם המשולש עצמו אינו מכיל נקודה נוספת. כלומר הוכחתי טענה חזקה יותר ממה שביקשת: לא רק שהגרף מישורי, אלא שהציור הוא מימוש של הגרף במישור ללא חיתוכים בין הקשתות. הוכחה שהגרף קשיר נובעת מהפתרון הראשון שלי לחידה המקורית: נניח שהגרף לא קשיר. נבחר נקודות A ו - C מרכיבים קשירים שונים כך שכל שאר הנקודות נמצאות בצד אחד של הישר AC (מדוע יש נקודות כאלה?). נבחר נקודה B כך שהזווית ABC מקסימלית. המעגל החוסם את ABC אינו מכיל נקודה נוספת, ולכן המשולש ABC מופיע - בסתירה לכך ש - A ו - C הן מרכיבים קשירים שונים.

 

[מספר6]

זה שהמשולשים אינם מכילים נקודות

בפנים שלהם, לא אומר שהמשולשים לא נחתכים

 

[עריסטו]

צודק

 

[עריסטו]

האלגוריתם שלך נותן דרך יפה

לבנות טריאנגולציה (חלוקה למשולשים) של מצולע קמור שיש בתוכו נקודות שהן קדקודי המשולשים.

 

[עריסטו]

../images/Emo163.gif בשביל זה מספיק שהמשולשים

עצמם לא יכילו נקודה נוספת - אין צורך להתייחס למעגל החוסם.

 

[מספר6]

תודה על המחמאה

אבל אני חייב להודות שהאלגוריתם הוא לא שלי אלא של Delaunay. הטריאנגולציה של דלוני

היא מבנה חשוב ובעל שימושים רבים בגיאומטריה חישובית.