אלגוריתם עטיפת המתנה

צעדת ג'רוויס או אלגוריתם עטיפת המתנה הוא אלגוריתם למציאת הקמור של נקודות במישור.

האלגוריתם נקרא על שם ריי ג'רוויס שפרסם את האלגוריתם בשנת 1973, אף על פי שהאלגוריתם התגלה במקביל בתקופה זו על ידי מספר חוקרים.

סיבוכיות זמן הריצה של האלגוריתם היא (O(nh כאשר n הוא מספר הנקודות הכולל ו-h הוא מספר הנקודות שירכיבו את הקמור בסופו של דבר.

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

ניתן להשתמש באלגוריתם גם עבור מספר רב של ממדים.

קטגוריה:גאומטריה חישובית
קטגוריה:אלגוריתמים