neizod's speculation

insufficient data for meaningful answer

แผนภาพ Voronoi ที่เส้นขอบเป็นไฮเพอร์โบลา

Wednesday, May 13, 2020, 10:24 AM

เคยเขียนถึงแผนภาพ Voronoi ไปบ้าง (1, 2) ว่าแนวคิดมันคือการแบ่งแผนที่ออกเป็นเซลล์ เพื่อให้ข้อมูลว่าแต่ละเซลล์อยู่ใกล้กับจุดตั้งต้นจุดไหนมากที่สุด (มองจุดตั้งต้นเป็นสถานีดับเพลิงก็ได้ว่าจะแบ่งพื้นที่กันยังไงให้เวลาไฟไหม้แล้วรถดับเพลิงไปถึงจุดเกิดเหตุไวที่สุด)

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

แล้วถ้าวงกลมที่ล้อมรอบแต่ละสถานีมีจุดเริ่มต้นขยายตัวไม่พร้อมกันหละ (เช่น บางสถานีที่เมื่อได้ข่าวไฟไหม้แล้วสามารถตระเตรียมรถดับเพลิงให้ออกปฏิบัติงานได้เร็วก่อนสถานีอื่น) เช่นนี้แล้วขอบของแต่ละเซลล์จะมีหน้าตาเปลี่ยนแปลงไปเป็นอย่างไร?

ตัวอย่างแผนภาพ Voronoi แบบที่แต่ละจุดตั้งต้นเริ่มขยายวงกลมล่วงหน้าไปก่อนไม่รอเริ่มพร้อมกัน

ปัญหานี้เป็นหนึ่งในปัญหาที่แตกหน่องอกงามออกมา โดยมันมีชื่อเฉพาะว่าแผนภาพ Voronoi ที่ถูกเพิ่มน้ำหนักด้วยการบวก (additively weighted Voronoi diagram) ซึ่งสปอยล์คำตอบตรงนี้ก่อนเลยว่า ขอบเซลล์ที่ได้จะเป็นเส้นโค้งแบบไฮเพอร์โบลา!


พิจารณาสถานี $A$ กับ $B$ ซึ่งสถานี $A$ เริ่มต้นขยายวงกลมไปก่อนแล้วด้วยขนาด $R$ หน่วย และทั้งสองสถานีต้องขยายวงกลมเพิ่มอีก $r$ หน่วย วงกลมทั้งสองถึงจะมาชนกันที่จุดขอบระหว่างเซลล์จุดแรก หากสนใจจุด $C$ ซึ่งเป็นจุดขอบเมื่อขยายวงกลมเพิ่มไปอีก $t$ หน่วย คำถามคือตำแหน่งของจุด $C$ จะอยู่ ณ พิกัดใด?

สามเหลี่ยมสำหรับวิเคราะห์ปัญหานี้

ดูเผินๆ เหมือนจะคำนวณตำแหน่ง $C$ ได้ยากมาก แต่เราสามารถเริ่มต้นที่การลากเส้นผ่านจุด $C$ ไปตั้งฉากกับ $\overline{AB}$ เพื่อสร้างจุดตัด $D$ ขึ้นมา ซึ่งก็คือเราจะได้ว่า $\overline{AB} = \overline{AD} + \overline{BD}$

นอกจากนี้ เรายังจะได้สมบัติพื้นฐานของสามเหลี่ยมมุมฉาก $\triangle ADC$ และ $\triangle BDC$ มาใช้อีกด้วย คือ

ซึ่งจะทำให้ได้ว่า

ย้ายข้างและจัดรูป ก็จะได้คำตอบ

เมื่อรู้ $\overline{AD}$ ก็ง่ายแล้ว เพราะย้อนกลับไปใช้พีทาโกรัสหา $\overline{CD}$ โดยตรงได้ทันที


ตอนนี้เพื่อความง่ายในการวิเคราะห์ต่อ สมมติให้ $\overline{AB}$ ขนานกับแกน $X$ โดยให้ $A=\left(\frac{-R-2r}2,0\right)$ และ $B=\left(\frac{R+2r}2,0\right)$ แล้วแทนค่าความยาวด้านต่างๆ ลงไปเพื่อหาตำแหน่งของ $C=(x,y)$ เริ่มจากหาตำแหน่งในแกน $X$ ก่อน ก็จะได้ว่า

และเมื่อหาตำแหน่งในแกน $Y$ ก็จะได้

ถึงจะได้ข้อมูลตำแหน่งมาครบก็อาจจะยังมองไม่ชัดถึงหน้าตาสมการว่าเป็นไฮเพอร์โบลาได้อย่างไร แต่ถ้าอดทนจัดรูปต่อไปอีกหน่อยก็จะเห็นว่าสมการข้างต้นมันสามารถกลายเป็น

ซึ่งก็คือไฮเพอร์โบลา ที่มีค่า $a=\frac{R}2, c=\frac{R+2r}2$ นั่นเอง


ป.ล. อันที่จริงไม่ต้องวิเคราะห์ยืดยาวก็ได้ เพราะวิธีการข้างต้นก็เป็นนิยามการสร้างไฮเพอร์โบลาอยู่แล้ว 🤪