ขั้นตอนวิธีแบบห่อของขวัญ

ขั้นตอนวิธีแบบห่อของขวัญ (อังกฤษ: Gift Wrapping Algorithm) คือวิธีในทาง เรขาคณิตเชิงคำนวณ ที่ใช้ในการคำนวณหา คอนเวกซ์ฮัลล์

 ประวัติ 
ขั้นตอนวิธีแบบห่อของขวัญมีชื่อเรียกอีกอย่างหนึ่งว่า การเดินแถวของจาร์วิส (อังกฤษ: Jarvis' March) เพื่อเป็นเกียรติแก่ อาร์.เอ. จาร์วิส ผู้นำขั้นตอนวิธีนี้ออกเผยแพร่ในปี พ.ศ. 2516 (หลังจาก โรนัลด์ เกรแฮม นำเสนอเกรแฮมสแกนหนึ่งปี)

 ขั้นตอนวิธี 

เริ่มจากให้ i = 0 และให้ p0 คือจุดสุดขีดจุดหนึ่ง ซึ่งทราบแน่นอนว่าอยู่บนคอนเวกซ์ฮัลล์ เช่น จุดบนสุด จากนั้น เลือกจุด pi+1 โดย pi+1 คือจุดที่ให้มุมกว้างที่สุดเทียบกับ Pi (อาจเป็นทิศทวนเข็มนาฬิกาหรือตามเข็มนาฬิกาก็ได้) ทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะได้ ph = p0 คือวนกลับมาจนครบจุดเริ่มต้นนั่นเอง ()

 รหัสเทียม 

 jarvis(S)                      // รับ S ที่เป็นเซทของจุด
   pointOnHull = จุดสุดขีดจุดหนึ่ง    // ตั้งค่า p0 ด้วยจุดสุดขีดจุดหนึ่ง
   i = 0                       // เริ่ม i = 0
   repeat
      P[i] = pointOnHull       // เพิ่มค่า pi ลงไปในอาเรย์ของคำตอบ P ช่องที่ i
      endpoint = S[0]          // ตั้งค่าเริ่มต้นสำหรับการหาจุดต่อไปบนคอนเวกซ์ฮัลล์
      for j from 1 to |S|-1    // ตรวจสอบทุกจุด
         if (pointOnHull.angle(S[j]) > pointOnHull.angle(endpoint))
            endpoint = S[j]    // ถ้าหากมุมของจุดใหม่กว้างกว่าเทียบกับจุดเดิมที่เลือกไปในรอบก่อน ให้เปลี่ยนจุดที่เลือกใหม่
      i = i+1
      pointOnHull = endpoint   // ตั้งค่าจุด pi+1 ให้เป็นจุดหลักสำหรับรอบหน้า
 until endpoint == P[0]        // ทำซ้ำจนกว่าจะครบรอบ

 ประสิทธิภาพ 
เนื่องจากเวลาในการหามุมสำหรับแต่ละจุดเป็นค่าคงที่ (O(1)) และการเปรียบเทียบมุมสำหรับทุกคู่จุดจะใช้เวลา O(n) สรุปว่าเราสามารถหาจุดๆหนึ่งบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(n) และหากมีจุดบนคอนเวกซ์ฮัลล์เป็นจำนวน h จุดแล้ว สรุปได้ว่าการเดินแถวของจาร์วิสจะสามารถหาจุดทุกๆจุดบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(nh)

 การนำไปใช้ 
โดยปกติแล้ว การเดินแถวของจาร์วิสนั้นจะสามารถทำงานได้เร็วกว่าเกรแฮมสแกน โดยกรณีที่เลวที่สุดคือกรณีที่ทุกจุดอยู่บนคอนเวกซ์ฮัลล์ เช่น รูปวงกลม

 อ้างอิง 



 แหล่งข้อมูลอื่น 
 ขั้นตอนวิธีการห่อของขวัญในระดับตั้งแต่สองมิติขึ้นไป 
 แบบจำลองคอนเวกซ์ฮัลล์ 
 ข้อมูลเพิ่มเติมจากมหาวิทยาลัยเคนท์สเตท
 รหัสในภาษา C++
 http://www.chrisharrison.net/projects/convexHull/index.html

หมวดหมู่:พอลิโทป
หมวดหมู่:ขั้นตอนวิธีแก้ปัญหาเปลือกนูน