ขั้นตอนวิธีของฟอร์จูน

ขั้นตอนวิธีของฟอร์จูน คือขั้นตอนวิธีแบบเส้นกวาด (sweep line algorithm) ที่ใช้สำหรับสร้างแผนภาพโวโรนอย จากเซตของจุดบนระนาบ โดยใช้เวลา $O(n*log(n))$ ซึ่งคิดค้นขึ้นโดย Steven Fortune ในปี 1986

ประวัติ

ในอดีตหลายปีที่ผ่านมาได้มีผู้ที่คิดค้นขั้นตอนวิธีสำหรับการสร้างแผนโวโรนอยโดยใช้เวลาในการคำนวณเป็น $O(n^{2})$ ในเวลาต่อมา ได้มีผู้คิดค้นขั้นตอนวิธีที่รวดเร็วกว่า โดยใช้เวลาในการคำนวณเป็น $O(n*log(n))$ โดยขั้นตอนวิธีดังกล่าว คิดโดยพื้นฐานของขั้นตอนวิธีแบบแบ่งแยกและเอาชนะ (divide and conquer) แต่วิธีการนี้ มีความซับซ้อนมาก และยากที่จะทำความเข้าใจ ด้วยเหตุนี้ ภายหลัง Steven Fortune จึงได้คิดค้นวิธีเส้นกวาดนี้ขึ้นมาเพื่อแก้ปัญหาดังกล่าว โดยยังคงใช้เวลาในการคำนวณเท่าเดิม คือ $O(n*log(n))$

หลักการทำงานของขั้นตอนวิธีเส้นกวาด

วิธีการนี้จะมีสองส่วนที่ต้องสนใจคือเส้นกวาด (sweep line) และเส้นคลื่นทะเล (beach line) แผนภาพโวโรนอยจะค่อยๆถูกสร้างขึ้น ตามแนวเส้นกวาด ที่กวาดไซท์ต่างๆ ไป จากบนลงล่าง โดยจะค่อยๆ พิจารณาทีละไซท์ ตามที่เส้นกวาด กวาดไปพบ นั่นคือ ทำการพิจารณาไซท์ต่างๆ ที่อยู่ด้านบนของเส้นกวาดก่อน ส่วนไซท์ที่อยู่หลังเส้นกวาด จะยังไม่นำมาพิจารณา

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

อีกหนึ่งจุดที่สำคัญคือจุดหยุด (break point) คือ ตำแหน่งที่เกิดจากการส่วนโค้ง (arc) ของสองเส้นคลื่นทะเลมาบรรจบกัน อยู่บนเส้นเชื่อมโวโรนอย (voronoi edge) โดยมันจะเลื่อนตามเส้นเชื่อมลงมาเรื่อยๆ ตามที่เส้นคลื่นทะเลเลื่อนลงมา ซึ่งจุดนี้เป็นจุดที่มีระยะห่าง จากจุดถึงไซท์ที่เส้นคลื่นทะเลมาบรรจบกัน และ จากจุดถึงเส้นกวาด เท่ากัน

ลักษณะการเคลื่อนตัวของทั้งสองเส้น เพื่อสร้างแผนภาพจะเป็นดังนี้

เหตุการณ์สำคัญ

ระหว่างการเคลื่อนที่ของทั้งสามจุดนี้ จะมีเหตุการณ์สำคัญ(significant event) ที่ทำให้เกิดการเปลี่ยนแปลงของโครงสร้าง และการเปลี่ยนแปลงของลักษณะของเส้นคลื่นทะเล ที่ต้องพิจารณาด้วย คือ

สถานะของเส้นกวาด - ตำแหน่งปัจจุบันของเส้นกวาด (พิกัด y) ซึ่งเป็นตัวกำหนดเส้นคลื่นทะเล
เหตุการณ์การพบไซท์ - เส้นกวาดเคลื่อนที่จนพบไซท์ ทำให้เกิดการแทรกเส้นโค้งเข้ามาที่เส้นคลื่นทะเลเดิม ทำให้เส้นคลื่นทะเลเดิมถูกแยกเป็นสองส่วน ดังภาพ

เหตุการณ์การเกิด vertex (circle events) - เมื่อความยาวของเส้นโค้งพาราโบล่าหดจนเหลือ 0 (เส้นโค้งหายไป) จะเกิด voronoi vertex ที่จุดศูนย์กลางของวงกลมที่มีเส้นรอบวงสัมผัสไซท์ รอบตัว 3 ไซท์ และ เส้นกวาด

การเก็บสถานะของแผนภาพโวโรนอย เส้นกวาด และ เส้นคลื่นทะเล

สถานะของแผนภาพโวโรนอย ใช้ Doubly linked list (D) ทำให้เราสามารถสำรวจ ส่วน เซลล์ และ vertices ของแผนภาพได้

สถานะของเส้นคลื่นทะเล

ใช้ Balanced Binary Tree (T) • โนดภายในต้นไม้ แสดงถึงจุดหยุดระหว่างสองเส้นโค้งคลื่นทะเล • ใบของต้นไม้แสดงถึงเส้นโค้ง โดยเส้นโค้งถูกแสดงจากไซท์ของตนเอง

สถานะของเส้นกวาด ใช้ Priority event queue (Q)

ขั้นตอนวิธี

กำหนดค่าเริ่มต้น

Event queue Q ß เหตุการณ์การพบ site ทุกเหตุการณ์
Binary search tree T ß Æ
Doubly linked list D ß Æ

2. While Q not Æ,

Remove event (e) from Q with largest y-coordinate
ลบเหตุการณ์ที่มีค่าพิกัด y สูงสุด ออกจากคิว
HandleEvent(e, T, D)

การจัดการกับเหตุการณ์ต่างๆ

การจัดการกับเหตุการณ์การพบ site

ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์

การจัดการกับเหตุการณ์การเกิด vertex

เพิ่ม vertex ใน doubly linked list
ลบเส้นโค้งที่หายไป
เพิ่มข้อมูลเส้นเชื่อม ใหม่ที่เกิด ลงใน doubly linked list
ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์

วิเคราะห์ประสิทธิภาพเชิงเวลา

การจัดการกับเหตุการณ์การพบ site

ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์จะได้
O(logn)
O(1)
O(1)
O(1)

การจัดการกับเหตุการณ์การเกิด vertex

เพิ่ม vertex ใน doubly linked list
ลบเส้นโค้งที่หายไป
เพิ่มข้อมูลเส้นเชื่อมใหม่ที่เกิด ลงใน doubly linked list
ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์จะได้
O(logn)
O(1)
O(1)
O(1)

สรุป

แต่ละ site ใหม่ จะทำให้เกิดเส้นโค้งใหม่ได้มากสุด สองเส้น

เส้นคลื่นทะเลสามารถมีเส้นโค้งได้มากสุด 2n-1 เส้น
มากสุด $O(n)$ สำหรับ site และ เหตุการณ์การเกิด vertex ในคิว
การจัดการทำเหตุการณืทั้งสองแบบใช้เวลา $O(log(n))$

ดังนั้น เวลาทั้งหมดที่ใช้ คือ $O(n*log(n))$

รหัสเทียม

let * (z) be the transformation * (z) = (zx,zy + d(z)), where d(z) is a parabola with minimum at z
let T be the "beach line"
let Rp be the region covered by site p.
let Cpq be the boundary ray between sites p and q.
let p1,p2,...,pm be the sites with minimal y-coordinate, ordered by x-coordinate

create initial vertical boundary rays

while not IsEmpty(Q) do
    p ← DeleteMin(Q)
    case p of
    p is a site in  * (V):
        find the occurrence of a region  * (Rq) in T containing p,
          bracketed by Crq on the left and Cqs on the right
        create new boundary rays   and   with bases p
        replace  * (Rq) with   in T
        delete from Q any intersection between Crq and Cqs
        insert into Q any intersection between Crq and
        insert into Q any intersection between   and Cqs
    p is a Voronoi vertex in  * (V):
        let p be the intersection of Cqr on the left and Crs on the right
        let Cuq be the left neighbor of Cqr and
          let Csv be the right neighbor of Crs in T
        create a new boundary ray   if qy = sy,
          or create   if p is right of the higher of q and s,
          otherwise create
        replace Cqr, * (Rr),Crs with newly created Cqs in T
        delete from Q any intersection between Cuq and Cqr
        delete from Q any intersection between Crs and Csv
        insert into Q any intersection between Cuq and Cqs
        insert into Q any intersection between Cqs and Csv
        record p as the summit of Cqr and Crs and the base of Cqs
        output the boundary segments Cqr and Crs
    endcase
endwhile
output the remaining boundary rays in T

อ้างอิง