ויקיפדיה

קמור – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
YurikBot (שיחה | תרומות)
85,149 עריכות
מ robot Adding: sl
עריכה
שורה 1:
ב[[מתמטיקה]], ה'''קְמוֹר''' של גוף או אוסף של גופים הוא ה[[גוף קמור|גוף הקמור]] המינימלי המכיל אותם. במקרה הפרטי שבו אוסף הגופים הוא אוסף של [[נקודה (גאומטריה)|נקודות]] ב[[מישור (גאומטריה)|מישור]] הדו-ממדי, ניתן לחשוב על הקמור כעל גומייה שנמתחה כך שתקיף את כל הנקודות, ולאחר מכן שוחררה עליהן.
 
ישנם מספר [[אלגוריתם|אלגוריתמים]] העוסקים במציאת גוף קמור, הן במקרים המיוחדים של שניים ושלושה ממדים, והן במקרה של מספר ממדים כלשהו. שני אלגוריתמים ידועים למציאת קמור של אוסף נקודות במישור הדו ממדי הם [[הסריקה של גראהם]] ו[[הצעדה של ג'ארביס]]. החסם התחתון על זמן מציאת הקמור של אוסף בן <math>\ n</math> נקודות במקרה הגרוע הוא <math>\ n\log n</math>. ניתן להצדיק חסם זה על ידי כך שבאמצעות אלגוריתם שמוצא קמור ניתן למיין סדרת נקודות, והוכח כי [[מיון]] חסום מלמטה במקרה הכללי (בו אין מידע נוסף על הנקודות) על ידי <math>\ n\log n</math>. עבור מרחב ממימד <math>\ d>3</math> החסם התחתון הוא <math>\ n^{\left[d/2\right]}</math> בשל [[סיבוכיות]] ה[[פוליהדרון]] שיווצר.
 
==קישורים חיצוניים==
* [http://www.cs.princeton.edu/~ah/alg_anim/version1/ConvexHull.html הדגמה של קמור של קבוצת נקודות במישור]
 
[http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html הדגמה נוספת גם בתלת מימד ואלגוריתמים נוספים]
 
{{קצרמר מתמטיקה}}
אוחזר מתוך "https://he.wikipedia.org/wiki/קמור"