پیمایش گراهام
پیمایش گراهام روشی است برای محاسبه پوش محدب مجموعه متناهی از نقاط صفحه که پیچیدگی زمانی آن است. این الگوریتم به افتخار رونالد گراهام که نسخهٔ اصلی الگوریتم را در ۱۹۷۲ منتشر کرد نامگذاری شده‌است. این الگوریتم تمامی راس‌های مرزی پوش محدب به صورت مرتب می‌یابد.
اولین گام در این الگوریتم یافتن نقطه‌ای با کمترین y است. اگر چند نقطه با کمترین y وجود داشت، در این مجموعه نقطه با کمترین x انتخاب خواهد شد. این نقطه را P می‌نامیم. این مرحله به اندازه (O(n زمان می‌برد که n تعداد نقاط می‌باشد.
سپس مجموعه نقاط باید بر حسب افزایش زاویه‌ای که آن‌ها و نقطه P با محور X می‌سازند، مرتب شوند. از هر الگوریتم مرتب‌سازی برای این این مرحله می‌توان استفاده کرد به عنوان مثال مرتب‌سازی هرمی که پیچیدگی زمانی آن (O(n log n است.
برای افزایش سرعت محاسبه لازم نیست زاویهٔ واقعی که این نقاط با محور X می‌سازند محاسبه شود در عوض، محاسبه کسینوس این زاویه کافیست.
این الگوریتم با در نظر گرفتن هر نقطه در آرایه مرتب شده پیش می‌رود. برای هر نقطه این موضوع را در نظر می‌گیرد که آیا حرکت از دو نقطه‌ای که قبلاً در نظر گرفته به این نقطه یک چرخش به چب بوده یا چرخش به راست. اگر چرخش به راست باشد به این معناست که نقطه دوم به آخر بخشی از بدنه محدب نمی‌باشد و باید حذف شود. این فرایند تا زمانی ادامه می‌یابد که مجموعه سه نقطه آخر چرخش به راست باشد. به محض اینکه با یک چرخش به چپ مواجه شود الگوریتم به سراغ نقطه بعدی در آرایه مرتب شده می‌رود. (اگر در هر مرحله سه نقطه در یک راستا باشند، ممکن است انتخاب شود یا دور انداخته شود چون در برخی برنامه‌ها لازم است همه نقاط روی مرز بدنه محدب پیدا شوند.
بازهم برای تعیین اینکه آیا سه نقطه تشکیل یک چرخش به چپ را می‌دهند یا چرخش به راست، نیازی نیست زاویه واقعی میان دو پاره خط محاسبه شود و در واقع می‌توانید تنها با حسابی ساده به این هدف برسید. برای سه نقطه (x1,y1)، (x2,y2)و (x3,y3)، محاسبه جهت ضرب خارجی دو برداری که با نقاط (x1,y1) , (x2,y2)و (x1,y1), (x3,y3)تعریف می‌شوداز طریق تعیین علامت عبارت (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1)میسر است. اگر این عبارت صفر شد نقاط هم راستا هستند. اگر مثبت شد نقاط یک گردش به چپ و در غیر اینصورت یک گردش به راست را تشکیل می‌دهند.
این فرایند در نهایت به نقطه‌ای که از آن شروع کرده‌است بازمی گردد، که در آن نقطه الگوریتم به پایان رسیده‌است و پشته شامل نقاط روی بدنه محدب در خلاف جهت عقربه‌های ساعت می‌باشد.
مرتب سازی نقاط دارای پیچیدگی زمانی (O(n logn می‌باشد. در حالی که ممکن است به نظر برسد پیچیدگی زمانی حلقه از O(n2) می‌باشد. زیرا برای هر نقطه به عقب برمی گردد تا چک کند آیا هر یک از نقاط قبلی چرخش به راست ایجاد می‌کنند، اما در واقع از (O(n می‌باشد زیرا هر نقطه در نهایت از هر جهت چه گردش به راست و چه گردش به چپ، دو بار در نظر گرفته می‌شود. هر نقطه فقط یک بار به عنوان نقطه (x2,y2)در گردش به چپ در نظر گرفته می‌شود (زیرا الگوریتم به سراغ نقطه (x3,y3) بعد از آن می‌رود), و هم چنین به عنوان نقطه (x2,y2)در گردش به راست (زیرا نقطه (x2,y2) حذف می‌شود). بنابراین پیچیدگی زمانی کلی برابر است با (O(n logn. ابتدا تعریف
سپس نتایج در آرایه points ذخیره می‌شود.
این شبه کد از کتاب Sedgewick and Wayne's Algorithms چاپ چهارم گرفته شده‌است.
1. ^ De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars (2008). Computational Geometry Algorithms and Applications. Berlin: Springer. pp. 2–14. doi:10.1007/978-3-540-77974-2. .
2. ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993). "Optimal double logarithmic parallel algorithms based on finding all nearest smaller values". Journal of Algorithms 14 (3): 344–370. doi:10.1006/jagm.1993.1018. Cormen, Thomas H. ; Leiserson, Charles E. , Rivest, Ronald L. , Stein, Clifford (2001) [1990]. "33.3: Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. pp. 949–955. .