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

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

การแก้ปัญหาด้วยสามัญสำนึก/สัญชาตญาณที่พึ่งพาการประมาณค่าเช่นนี้ไม่ใช่เรื่องผิดอะไร เพียงแต่ว่าสำหรับปัญหานี้แล้ววิธีการดังกล่าวยังถือว่ามีประสิทธิภาพที่ไม่ดีเท่าไหร่นัก เพราะเราสามารถหาคำตอบที่ดีที่สุดได้อย่างแม่นยำโดยไม่ต้องพึ่งพาการประมาณค่าเลย

แล้วเราจะหาคำตอบที่แม่นยำได้อย่างไร? ปรกติแล้วเมื่อเจอปัญหาที่มีข้อมูลจำนวน $n$ ชิ้นมาเกี่ยวข้อง เทคนิคหนึ่งที่เราใช้ได้บ่อยๆ ก็คือการพิจารณาปัญหาย่อยที่มีข้อมูลจำนวนน้อยก่อน หลังจากนั้นเมื่อแก้ปัญหาย่อยได้ก็ค่อยๆ ขยายขนาดของปัญหากลับมา พร้อมทั้งสังเกตหาวิธีการที่จะแปลงผลลัพธ์ให้กลับไปอยู่ในรูปทั่วไปสำหรับข้อมูลขนาด $n$ ชิ้นให้เจอ

เช่นเมื่อเราพิจารณากรณีที่ต้องการคลุมแค่หนึ่งจุด $P=\lbrace p_1\rbrace$ เราก็สร้างดิสก์รัศมีเป็นศูนย์ไว้ที่ตำแหน่ง $p_1$ เท่านั้นพอ เราเรียกกรณีนี้ว่าเป็นกรณีลดรูป (degenerate case) ที่ไม่มีอะไรน่าสนใจเป็นพิเศษจึงสามารถข้ามมันไปได้เลย

คลุมแค่สองจุด

เมื่อเรามีจุดสนใจสองจุด $P=\lbrace p_1,p_2\rbrace$ ดิสก์ที่เล็กที่สุดคือดิสก์ที่มีจุดศูนย์กลางอยู่ระหว่าง $p_1$ กับ $p_2$ พอดี โดยมีเส้นผ่านศูนย์กลางขนาดเท่ากับ $\abs{\overline{p_1p_2}}/2$ ซึ่งนี่เป็นดิสก์ที่มีขนาดเล็กที่สุดแล้ว เพราะเส้นผ่านศูนย์กลางก็คือส่วนที่กว้างที่สุดของดิสก์ หากเส้นผ่านศูนย์กลางสั้นกว่านี้ก็แปลว่าดิสก์จะไม่มีทางคลุมทั้ง $p_1$ และ $p_2$ พร้อมกันได้เลย

ข้อสังเกตสำคัญของการสร้างดิสก์ในปัญหานี้ ก็คือเราต้องการให้ทั้ง $p_1$ และ $p_2$ อยู่บนขอบดิสก์พอดีนั่นเอง เพื่อความสะดวกเราจะเรียกดิสก์ที่มีจุดสองจุดเป็นเส้นผ่านศูนย์กลางเช่นนี้ว่า $D(p_1,p_2)$

คลุมสามจุด

หลังจากได้กรณีสองจุดแล้ว กรณีสามจุดก็เปรียบได้ดังภาคต่อง่ายๆ ที่เราอาจนำเอาข้อสังเกตเดิมมาประยุกต์ใช้ได้ว่า ทั้งสามจุดใน $P=\lbrace p_1,p_2,p_3\rbrace$ นั้นควรอยู่บนขอบของดิสก์พอดี (เราจะเรียกดิสก์ที่มีสามจุดบนขอบเช่นนี้ว่า $D(p_1,p_2,p_3)$) อย่างไรก็ตามข้อสังเกตดังกล่าวก็อาจนับได้ว่าเป็นกับดักชั้นดี เพราะการจัดเรียงจุดบางรูปแบบนั้นเราสามารถใช้ดิสก์ที่มีสองจุดบนขอบก็พอ อีกจุดที่เหลือนั้นไม่จำเป็นต้องอยู่ขอบ แต่จะอยู่ภายในดิสก์ไปเลย (เห็นได้ชัดเมื่อทั้งสามจุดนั้นอยู่ในแนวเส้นตรงเดียวกัน – หรือสรุปเป็นกรณีทั่วไปได้ว่าเมื่อลากเส้นเชื่อมจุดทั้งสามแล้ว หากได้สามเหลี่ยมมุมป้าน จุดที่อยู่บนมุมป้านจะต้องอยู่ในดิสก์) ดังนั้นสำหรับกรณีนี้เราต้องพิจารณาแยกเป็นกรณีย่อยๆ โดยไปยืมการสร้างดิสก์จากกรณีคลุมแค่สองจุดมาช่วย

ตัวอย่างการคลุมสามจุด ที่การสร้างดิสก์ด้วยจุดทั้งสาม (สีแดง) เปลืองกว่าการใช้แค่สองจุด (สีน้ำเงิน)

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

คลุมสี่จุดขึ้นไป

ความดีงามของกรณีที่ผ่านมาก็คือว่าเราใช้จุดอย่างมากสุดแค่สามจุดบนขอบดิสก์ก็เพียงพอ นั่นคือ แม้ว่าเราจะมีจุดมากกว่าสามจุดบนขอบของดิสก์ เราก็สามารถเลือกหยิบแค่สามจุดใดๆ มาย้อนสร้างดิสก์นั้นได้เสมอ นี่ทำให้เราขยายการพิจารณาไปยังกรณีทั่วไปได้ ซึ่งก็คือเมื่อเราต้องการสร้างดิสก์ที่ครอบคลุมเซต $P=\lbrace p_1,\dots,p_n\rbrace$ เราสามารถยืมคำตอบของปัญหาย่อยที่คลุมแค่เซต $P’=\lbrace p_1,\dots,p_{n-1}\rbrace$ มาช่วยได้

ให้ $D_{n-1}$ แทนดิสก์ที่เป็นคำตอบของการคลุมเซต $P’$ เราจะถามว่าแล้ว $p_n$ นั้นอยู่ใน $D_{n-1}$ หรือไม่ หากคำตอบคือใช่เราก็ไม่ต้องทำอะไรต่อ เพราะว่าเราจะได้ดิสก์คำตอบที่คลุม $P$ ว่าก็คือ $D_n \gets D_{n-1}$ เลย แต่หากคำตอบคือไม่ เราจะวนลงไปทำปัญหาย่อยบน $P’$ อีกครั้ง เพียงแต่คราวนี้เราจะบังคับให้ดิสก์คำตอบนั้นมี $p_n$ อยู่บนขอบด้วยนั่นเอง

แนวคิดทั้งหมดสามารถแปลงเป็นโค้ดได้คร่าวๆ ดังนี้

def mini_disk(points, borders=()):
    if not points or len(borders) == 3:
        return disk(borders)
    p, *remains = points
    d = mini_disk(remains, borders)
    if p in d:
        return d
    return mini_disk(remains, borders+(p,))

ตัวอย่างการทำงานของอัลกอริทึมบนข้อมูลนำเข้า $n=7$ จุด

ความซับซ้อนของอัลกอริทึม

แล้วอัลกอริทึมข้างต้นมีความเร็วเป็นเท่าไหร่กันหละ? แม้ว่าฟังก์ชันเวียนเกิดนี้จะมีการ “แตกแขนง” ตอนเรียกตัวเองแยกเป็นสองกิ่ง (ครั้งแรกเพื่อสร้างดิสก์มาทดสอบ และครั้งที่สองเพื่อสร้างดิสก์แบบบังคับจุดหากทดสอบไม่ผ่าน) ทำให้ดูเผินๆ แล้วความซับซ้อนก็น่าจะบานปลายเป็น $O(2^n)$ แต่หากตั้งใจดูให้ดีจะเห็นฟังก์ชันนี้สามารถเกิดการแตกแขนงตามทางลึกได้เพียงแค่สามครั้งเท่านั้น ดังนั้นความเร็วของอัลกอริทึมนี้จริงๆ จึงเหลือแค่ $O(n^3)$ แทน!

แล้วเราสามารถปรับปรุงให้มันเร็วกว่านี้ได้อีกหรือเปล่า? สังเกตว่าที่ผ่านมาเราวิเคราะห์แบบกรณีแย่สุดที่คิดให้แต่ละชั้นของการเรียกใช้ฟังก์ชัน มันต้องแตกแขนงไปเรียกตัวเองเป็นสองกิ่งทั้งสิ้น ทั้งที่ความจริงแล้วหากเราโชคดี เราก็อาจเรียกตัวเองแค่ครั้งเดียวพอไม่ต้องแตกแขนงเลย (เช่น โชคดีเจอข้อมูลนำเข้าที่สามจุดแรกนั้นสร้างดิสก์คลุมจุดที่เหลือทั้งหมด) ดังนั้นความเร็วก็จะลดเหลือเพียงแค่ $O(n)$ ในกรณีที่ดีที่สุด

แน่นอนว่าเราไม่มีทางโชคดีได้อย่างนี้ทุกครั้งไป (แต่ก็คงไม่มีทางโชคร้ายได้ทุกครั้ง) เช่นนั้นแล้วอัลกอริทึมดังกล่าวจะมีความเร็วโดยเฉลี่ยอยู่ที่เท่าไหร่กันหละ?

เราจะใช้เทคนิควิเคราะห์แบบย้อนกลับ ซึ่งก็คือเริ่มจากผลลัพธ์ที่เป็นดิสก์คลุมทั้ง $n$ จุดในตอนจบฟังก์ชัน แล้วย้อนกลับไปถามว่าที่จุดเริ่มต้นของฟังก์ชันนี้ ดิสก์ดังกล่าวครอบคลุมจุด $p_n$ มาก่อนหรือไม่ ซึ่งคำตอบนั้นจะขึ้นกับจำนวนจุดบนขอบดิสก์ที่เราเลือกตรึงไว้จากฟังก์ชันเวียนเกิดในชั้นก่อนหน้า เช่น หากที่ชั้นก่อนหน้าเราตรึงจุดไว้แล้วสองจุด ก็แปลว่าในชั้นนี้จะเหลือที่ว่างที่เดียวให้ $p_n$ สามารถอยู่บนขอบดิสก์ได้ ซึ่งก็คือมีโอกาสเกิด $1/n$ กลับกันหากชั้นก่อนหน้าเรายังไม่เคยตรึงจุดใดเอาไว้ก่อนเลย จะทำให้ในชั้นนี้จุด $p_n$ มีโอกาสถึง $3/n$ ที่จะอยู่บนขอบของดิสก์ที่ต้องการนั่นเอง

เราจะเขียนความสัมพันธ์เวียนเกิด $t_k(n)$ ที่วัดความเร็วของการเรียกฟังก์ชันด้วยข้อมูลนำเข้า $n$ จุด โดยมีจุดที่ถูกตรึงไว้บนขอบดิสก์แล้ว $3{-}k$ จุด ดังนั้นฟังก์ชันข้างต้นจึงถูกถอดความเป็นความสัมพันธ์เวียนเกิดได้ว่า

แน่นอนว่า $t_0(n)\le1$ จึงทำให้ได้ว่าเมื่อไล่แก้สมการเวียนเกิดไปเรื่อยๆ จะได้ $t_3(n)\le10n$ หรือสรุปได้ว่า อัลกอริทึมดังกล่าวมีค่าคาดหวังว่าจะทำงานด้วยความเร็วเป็นเชิงเส้นเทียบกับขนาดของข้อมูลนำเข้านั่นเอง

ในทางปฎิบัติ เราสามารถแก้ไขโค้ดข้างต้นเพียงเล็กน้อย ซึ่งก็คือสุ่มสลับลำดับจุดใน $P$ ทั้งหมดก่อนที่จะเรียกใช้งานฟังก์ชัน mini_disk เท่านี้ก็เพียงพอที่จะทำให้เราได้ความเร็วเฉลี่ยเป็น $O(n)$ แล้ว

อัลกอริทึมข้างต้นถูกนำเสนอโดย Emo Welzl ในปี 2005 ซึ่งเขียนออกมาเป็นโค้ดได้เรียบง่ายสั้นกระชับ อย่างไรก็ตามการวิเคราะห์ความซับซ้อนอาจจะยากหน่อย เพราะมันอิงอยู่บนฟังก์ชันเวียนเกิดที่ทำงานค่อนข้างแตกต่างจากฟังก์ชันเวียนเกิดอื่นๆ ที่เคยเห็นมา ซึ่งสำหรับใครที่อ่านมาถึงจุดนี้แล้วยังไม่ค่อยเข้าใจ อาจลองไปอ่านบทที่ 4.7 จากหนังสือ Computational Geometry: Algorithms and Applications เพิ่มเติมได้ ซึ่งหัวใจของอัลกอริทึมก็ทำงานเหมือนกันเนี่ยแหละ แต่เค้าจัดรูปฟังก์ชันเวียนเกิดข้างต้นให้กลายเป็นฟังก์ชันแบบวนลูปแทน และส่งผลให้วิเคราะห์เวลาการทำงานออกมาได้เข้าใจง่ายกว่านี้(มั้ง)

รายละเอียดการสร้างดิสก์

โค้ดข้างต้นนั้นยังรันจริงไม่ได้ (แม้จะเขียนเป็น Python อย่างถูกต้องทุกอย่างก็ตาม) เพราะมันยังขาดรายละเอียดสำคัญคือการสร้างดิสก์จากจุดขอบ ซึ่งกรณีที่ยากที่สุดก็คือเมื่อมีจุดขอบอยู่บนดิสก์สามจุด $\lbrace p_1,p_2,p_3 \rbrace$ นั่นเอง

มองในเชิงเรขาคณิตสังเคราะห์แล้ว นี่อาจไม่ใช่คำถามที่ยากเท่าไหร่ เพราะเราก็แค่สร้างเส้น $L_1$ ที่ตั้งฉากกับ $\overline{p_1p_2}$ และเส้น $L_2$ ที่ตั้งฉากกับ $\overline{p_2p_3}$ แล้วหลังจากนั้นก็แค่หาจุดตัดของ $L_1$ กับ $L_2$ ก็จะได้จุดศูนย์กลางของวงกลมแล้ว

การสร้างดิสก์/วงกลมที่มีจุดสามจุดอยู่บนขอบ

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

เราอาจเปลี่ยนไปพิจารณาสมการวงกลมแทน โดยให้ข้อมูลนำเข้า $p_i=(x_i,y_i)$ สำหรับ $i\in\lbrace1,2,3\rbrace$ และให้ตัวแปรจุดศูนย์กลางของวงกลมคือ $f=(x,y)$ พร้อมรัศมีวงกลมเท่ากับ $r$ ดังนั้นแล้วเราจะได้ชุดของสมการออกมาว่า

ซึ่งก็คือระบบสมการสามตัวแปร (ที่เราต้องการหาค่า $x,y,r$) นั่นเอง อย่างไรก็ตามเรายังทำงานกับสมการนี้ได้ยาก แต่ถ้าเรากระจายกำลังสองออกมาจะเห็นว่า

ดูเผินๆ แล้วเหมือนกับว่ามันจะกลายเป็นระบบสมการห้าตัวแปร แต่จุดสังเกตสำคัญคือ $x^2,y^2$ นั้นเป็นตัวแปรที่ขึ้นกับ $x,y$ ดังนั้นเราสามารถจับ $x^2,y^2$ ไปแปะอยู่กับตัวแปร $r^2$ ได้ ซึ่งจะทำให้ได้สมการเมทริกซ์ออกมาว่า

ดังนั้นคำตอบตำแหน่งจุดศูนย์กลางวงกลมก็คือ

ส่วนรัศมี $r$ นั้นจะหาผ่านดีเทอร์มิแนนต์ในทำนองเดียวกันก็ได้ แต่ใช้พีทาโกรัสน่าจะง่ายกว่าเยอะ 😉

from math import inf, hypot
from collections import namedtuple

Point = namedtuple('Point', 'x y')
Disk = namedtuple('Disk', 'f r')
Disk.__contains__ = lambda s, p: hypot(s.f.x-p.x, s.f.y-p.y) <= s.r

def disk_degenerate(p=Point(inf, inf)):
    return Disk(p, 0)

def disk_two(p, q):
    return Disk(Point((p.x+q.x)/2, (p.y+q.y)/2), hypot(p.x-q.x, p.y-q.y)/2)

def disk_three(u, v, w):
    d = (v.y-w.y)*u.x + (w.y-u.y)*v.x + (u.y-v.y)*w.x
    a = (v.y-w.y)*hypot(*u)**2 + (w.y-u.y)*hypot(*v)**2 + (u.y-v.y)*hypot(*w)**2
    b = (w.x-v.x)*hypot(*u)**2 + (u.x-w.x)*hypot(*v)**2 + (v.x-u.x)*hypot(*w)**2
    f = Point(a/2/d, b/2/d)
    return Disk(f, hypot(f.x-u.x, f.y-u.y))

def disk(borders):
    fs = [disk_degenerate, disk_degenerate, disk_two, disk_three]
    return fs[len(borders)](*borders)

ปัญหาที่ใหญ่กว่านี้

ปัญหาดิสก์ปิดครอบนี้เป็นเพียงแค่ปัญหาขั้นพื้นฐานเริ่มต้นง่ายๆ ในเรขาคณิตเชิงคำนวณเท่านั้น โดยปัญหาในรูปทั่วไปของมันก็คือกลุ่มของปัญหา 1-ศูนย์กลาง (1-center) ที่เปลี่ยนวิธีการวัดระยะทาง (เช่น ใช้ระยะทางแบบ $L^1$ แทน) หรือพิจารณาให้แต่ละจุดมีน้ำหนักไม่เท่ากัน หรือพิจารณาในมิติที่สูงขึ้น

ในอีกทางหนึ่ง เราก็สามารถขยายขนาดปัญหาโดยการยินยอมให้มีศูนย์กลางได้หลายแห่งเช่นกัน ซึ่งก็คือปัญหาการปิดครอบด้วย $k$-ศูนย์กลาง (ซึ่งมีปัญหาย่อยๆ ต่างกันไป เช่น ปัญหาที่ตั้งโรงงาน (facility location problem) หรือการวิเคราะห์กลุ่มก้อน (cluster analysis) เป็นต้น) การเพิ่มเงื่อนไขโจทย์เช่นนี้ทำให้ปัญหายากกลายเป็น NP-hard และทำให้เราต้องหาเทคนิคในแนวทางอื่นมาช่วยหาคำตอบแทน เช่น การประมาณค่าคำตอบและวิเคราะห์ว่าผลลัพธ์จะไม่แย่เกินกี่เท่าของคำตอบที่ดีที่สุด

อ้างอิง

• Welzl, E. (2005, June). Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991 Proceedings (pp. 359-370). Berlin, Heidelberg: Springer Berlin Heidelberg.
• De Berg, M. (2000). Computational geometry: algorithms and applications. Springer Science & Business Media.

neizod

author