הצעדה של ג'ארביס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

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

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.