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

 

ישנם מספר [[אלגוריתם|אלגוריתמים]] העוסקים במציאת גוף קמור, הן במקרים המיוחדים של שניים ושלושה ממדים, והן במקרה של מספר ממדים כלשהו. שני אלגוריתמים ידועים למציאת קמור של אוסף נקודות במישור הדו ממדי הם [[הסריקה של גראהם]] ו[[הצעדה של ג'ארביס]]. החסם התחתון על זמן מציאת הקמור של אוסף בן <math>\ n</math> נקודות במקרה הגרוע הוא <math>\ n\log n</math>. ניתן להצדיק חסם זה על ידי כך שבאמצעות אלגוריתם שמוצא קמור ניתן למיין סדרת נקודות, והוכח כי [[מיון (מדעי המחשב)|מיון]] חסום מלמטה במקרה הכללי (בו אין מידע נוסף על האלמנטים הממוינים) על ידי <math>\ n\log n</math>. עבור מרחב מממד <math>\ d>3</math> החסם התחתון הוא <math>\ n^{\left[d/2\right]}</math> בשל [[סיבוכיות]] ה[[פוליהדרון]] שיווצר.

 

==ראו גם==