خوارزمية القفز والمشي

خوارزمية "القفز والمشي" هي خوارزمية لتحديد مواقع النقاط في التثليثات (مع أن معظم التحليلات النظرية أُجريت على تثليثات ديلاوناي العشوائية ثنائية وثلاثية الأبعاد ). والمثير للدهشة أن هذه الخوارزمية لا تحتاج إلى أي معالجة مسبقة أو هياكل بيانات معقدة باستثناء تمثيل بسيط للتثليث نفسه. يعود الفضل في تطوير خوارزمية "القفز والمشي" إلى لوسون (1977) وغرين وسيبسون (1978)، حيث يتم اختيار نقطة بداية عشوائية S ثم السير من S نحو نقطة الاستعلام Q مثلثًا تلو الآخر. ولكن لم تكن هناك تحليلات نظرية معروفة لهذه الخوارزميات السابقة حتى منتصف التسعينيات.

تختار خوارزمية "القفز والمشي" مجموعة صغيرة من نقاط العينة، وتبدأ المشي من أقرب نقطة عينة إلى النقطة Q حتى يتم العثور على المُجَسَّم البسيط الذي يحتوي على Q. كانت هذه الخوارزمية شائعة الاستخدام لفترة من الزمن، وقد قام ديفروي وموكي وزو بتقديمها رسميًا وتحليل أدائها على تثليث ديلاوناي العشوائي ثنائي الأبعاد في منتصف التسعينيات (نُشرت الورقة البحثية في مجلة Algorithmica عام 1998). أما تحليلها على تثليث ديلاوناي العشوائي ثلاثي الأبعاد فقد أجراه موكي وساياس وزو (ندوة ACM للهندسة الحسابية، 1996). في كلتا الحالتين، تم افتراض شرط حدودي ، وهو أن تكون النقطة Q بعيدة قليلاً عن حدود المجال المحدب الذي رُسمت عليه رؤوس تثليث ديلاوناي العشوائي. في عام 2004، أظهر ديفروي، لومير ومورو أنه في البعدين يمكن سحب شرط الحدود (ظهرت الورقة في الهندسة الحسابية: النظرية والتطبيقات، 2004).

تم استخدام Jump-and-Walk في العديد من حزم البرامج الشهيرة، على سبيل المثال، QHULL و Triangle و CGAL .

• غرين، بي جيه؛ سيبسون، آر. (1978)، "حساب تبليطات ديريشليه في المستوى"، مجلة الكمبيوتر ، 21 (2): 168-173 ، doi : 10.1093/comjnl/21.2.168 ، MR 0485467 .
• لوسون، سي. ( 1977)، "برنامج لاستيفاء سطح C1"، في رايس، جيه آر (محرر)، البرمجيات الرياضية III ، نيويورك: أكاديميك برس، ص 161-194 .
• ديفروي، لوك؛ لومير، كريستوف؛ مورو، جان ميشيل (2004)، "تحليل الوقت المتوقع لتحديد موقع نقطة ديلاوناي"، الهندسة الحسابية: النظرية والتطبيقات ، 29 (2): 61-89 ، doi : 10.1016/j.comgeo.2004.02.002 ، MR 2082208 .
• ديفروي، ل.؛ موكي، إي. بي.؛ تشو، بينهاي (1998)، "ملاحظة حول تحديد موقع النقاط في تثليثات ديلاوناي للنقاط العشوائية"، Algorithmica ، 22 (4): 477-482 ، CiteSeerX 10.1.1.15.8612 ، doi : 10.1007/PL00009234 ، MR 1701623 ، S2CID 3000041   .
• موكي، إرنست ب.؛ ساياس، إسحاق؛ تشو، بينهاي (1999)، "تحديد سريع لمواقع النقاط العشوائية دون معالجة مسبقة في تثليثات ديلاوناي ثنائية وثلاثية الأبعاد"، عدد خاص من ندوة ACM الثانية عشرة حول الهندسة الحسابية (فيلادلفيا، بنسلفانيا، 1996)، الهندسة الحسابية: النظرية والتطبيقات ، 12 ( 1-2 ): 63-83 ، doi : 10.1016/S0925-7721(98)00035-2 ، MR 1677599 .