קמור
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה, הקְמוֹר של גוף או אוסף של גופים הוא הגוף הקמור המינימלי המכיל אותם. במקרה הפרטי שבו אוסף הגופים הוא אוסף של נקודות במישור הדו-ממדי, ניתן לחשוב על הקמור כעל גומייה שנמתחה כך שתקיף את כל הנקודות, ולאחר מכן שוחררה עליהן.
ישנם מספר אלגוריתמים העוסקים במציאת גוף קמור, הן במקרים המיוחדים של שניים ושלושה ממדים, והן במקרה של מספר ממדים כלשהו. שני אלגוריתמים ידועים למציאת קמור של אוסף נקודות במישור הדו ממדי הם הסריקה של גראהם והצעדה של ג'ארביס. החסם התחתון על זמן מציאת הקמור של אוסף בן 
נקודות במקרה הגרוע הוא 
. ניתן להצדיק חסם זה על ידי כך שבאמצעות אלגוריתם שמוצא קמור ניתן למיין סדרת נקודות, והוכח כי מיון חסום מלמטה במקרה הכללי (בו אין מידע נוסף על הנקודות) על ידי . עבור מרחב ממימד 
החסם התחתון הוא ![\ n^{\left[d/2\right]}](../../../math/9/3/3/93316be1176687f2f59e6c6be8cfee95.png)
בשל סיבוכיות הפוליהדרון שיווצר.
[עריכה] קישורים חיצוניים
ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.
