الگوریتم بسته‌بندی هدیه

در هندسه محاسباتی، بسته‌بندی هدیه  الگوریتمی برای محاسبه پوش محدبِ مجموعه‌ای از نقاط است.

حالت دوبُعدی 
در حالت دوبُعدی این الگوریتم به راه‌پیمایی جارویس نیز مشهور است. جارویس در سال ۱۹۷۳، در مقاله‌ای این الگوریتم را به چاپ رساند. علت انتخاب نام بسته‌بندی هدیه برای این الگوریتم به این دلیل است که در فضای دوبُعدی نحوه عملکرد این روش مانند پیچاندان کاغذ کادو به دور مجموعه نقاط و احاطه کردن آن‌ها توسط اضلاعی است که به ترتیب به عنوان خروجی الگوریتم حاصل می‌شوند.

الگوریتم 
در نهابت خروجی الگوریتم دنباله‌ای به صورت  است که هر عضو این دنباله، یکی از رئوس پوش محدب را تشکیل دهد. در ابتدا پایین‌ترین نقطه مجموعه را که از وجود آن در پوش محدب اطمینان داریم، به عنوان نقطه p0 انتخاب می‌کنیم. راًس بعدی انتخاب شده که p1 نام دارد بایستی کوچکترین زاویه در مختصات قطبی نسبت به نقطه p0 را داشته باشد. (در صورتی که چند نقطه در این شرایط صدق کردند دورترین نقطه را انتخاب کنیم) به‌طور مشابه نقطه p2 کوچکترین زاویه قطبی را نسبت به p1 دارد. زمانی که با تکرار این روند، به راًس pk که بالاترین راًس است رسیدیم، زنجیره راستِ پوش محدب ساخته شده‌است. در شرایط مساوی، pk را دورترین نقطه انتخاب می‌کنیم. اکنون برای ساختن زنجیره چپ، می‌بایستی با شروع از pk، راًس pk+1 را طوری انتخاب کنیم که کوچکترین زاویه قطبی را از محور منفی X نسبت به pk داشته باشد. این روند را آن‌قدر ادامه می‌دهیم تا مجدداً به p0 برسیم و پوش محدب کامل شود. البته این الگوریتم را بدون ساختن زنجیره راست و چپ نیز می‌توان پیاده‌سازی کرد، ولی مزیت پیاده‌سازی به وسیله ساختن زنجیره‌های چپ و راست این است که نیازی به محاسبه دقیق زاویه‌های قطبی نبست و به روش ساده‌ای می‌توان زوایا را با هم تنها مقایسه کرد.
پیاده‌سازی بدون زنجیره‌های چپ و راست بدین صورت است: نقطه شروع را به طریق مشابه بالا انتخاب می‌کنیم. سپس با فرض اینکه تا این مرحله، آخرین نقطه انتخاب‌شده pi است، نقطه pi+1 را طوری انتخاب می‌کنیم که همه نقاط دیگر در یک سمتِ خط pipi+1 باشند. این نقطه با  عملیات، به وسیله مقایسه مختصات قطبی نقاط با pi مشخص می‌شود. این عملیات را آنقدر تکرار می‌کنیم تا به p0 = ph برسیم.

شبه کد 
  Jarvis(s)
      pointOnHull = leftmost point in S
      i = 0
      repeat
            P[i] = pointOnHull
            endpoint = S[0]         // initial endpoint for a candidate edge on the hull
            for j from 1 to |S|
                if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
                    endpoint = S[j]   // found greater left turn, update endpoint
            i = i+1
            pointOnHull = endpoint
      until endpoint == P[0]      // wrapped around to first hull point

پیچیدگی 
اگر تعداد نقاط مجموعه برابر با n و تعداد نقاط روی پوش محدب برابر با h باشد، پیچیدگی زمانی این الگوریتم از  است؛ زیرا برای هر نقطه p که عضو پوش محدب باشد باید زاویه قطبی  راًس دیگر نسبت به p، با هم مقایسه شوند که هر هر عملیات مقایسه از  است. چون h نقطه روی پوش محدب قرار دارند بنابراین زمان اجرا از  است.
این الگوریتم در صورتی از لحاظ زمانی کارا خواهد بود که n عددی بزرگ نباشد یا اینکه h نسبت به n کوچک باشد. به عبارت دقیق‌تر اگر ، این الگوریتم از الگوریتم پیمایش گراهام سریع تر است. در غیر این‌صورت این الگوریتم در مقایسه با سایر روش‌ها به‌طور مجانبی کُندتر خواهد بود که در نتیجه از الگوریتم‌های مشابه که زمان اجرای کمتری دارند استفاده می‌شود؛ مانند الگوریتم چان که زمان اجرای آن از  است.

منابع 

 
 

الگوریتم‌ها
الگوریتم‌های پوش محدب
پوش‌های محدب
پلیتوپ‌ها
مجلات آکادمیک الزویر
مجله‌های علوم رایانه
نشریه‌های بنیان‌گذاری‌شده در ۱۹۷۱ (میلادی)
هندسه محاسباتی