คำอธิบาย รหัสเทียมของอัลกอริทึม^{[ 4 ]}

อนุญาต${\displaystyle \scriptstyle *(z)}$เป็นการเปลี่ยนแปลง${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$, ที่ไหน${\displaystyle \scriptstyle d(z)}$คือระยะทางแบบยุคลิดระหว่างzกับไซต์ที่ใกล้ที่สุด ให้T เป็น "แนวชายหาด" ${\displaystyle \scriptstyle R_{p}}$ให้ เป็นบริเวณที่ครอบคลุมโดยไซต์p${\displaystyle \scriptstyle C_{pq}}$ให้เป็นรังสีขอบเขตระหว่างไซต์pและqให้ ${\displaystyle \scriptstyle S}$ให้ เป็นชุดของไซต์ที่จะนำอัลกอริธึมนี้ไปใช้ ให้${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$ให้ X เป็นไซต์ที่สกัดจากS ที่มีพิกัด yน้อยที่สุดเรียงลำดับตามพิกัด x ให้ DeleteMin( X ) เป็นการกระทำในการลบไซต์ที่ต่ำที่สุดและซ้ายสุดของX (เรียงลำดับตาม y เว้นแต่ว่าไซต์ทั้งสองจะเหมือนกัน ในกรณีนั้นให้เรียงลำดับตาม x) ให้Vเป็นแผนที่โวโรนอยของSที่จะสร้างขึ้นโดยอัลกอริทึมนี้ ${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$สร้างรังสีขอบเขตแนวตั้งเริ่มต้น${\displaystyle \scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,C_{p_{m-1},p_{m}}^{0}}$${\displaystyle T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$ในขณะที่ Q ไม่ว่างเปล่าให้ ลบ ค่าต่ำสุดของQ ออกหากp ของpเป็นไซต์ใน${\displaystyle \scriptstyle *(V)}$: ค้นหาการปรากฏของภูมิภาค${\displaystyle \scriptstyle *(R_{q})}$ในTที่มีp อยู่ ถูกล้อมกรอบโดย${\displaystyle \scriptstyle C_{rq}}$ทางด้านซ้ายและ${\displaystyle \scriptstyle C_{qs}}$ทางด้านขวา สร้างรังสีขอบเขตใหม่${\displaystyle \scriptstyle C_{pq}^{-}}$และ${\displaystyle \scriptstyle C_{pq}^{+}}$โดยใช้ฐานp แทนที่${\displaystyle \scriptstyle *(R_{q})}$กับ${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$ในT ให้ลบ ส่วนที่ทับซ้อนกันทั้งหมดออกจากQ${\displaystyle \scriptstyle C_{rq}}$และ${\displaystyle \scriptstyle C_{qs}}$แทรก จุดตัดใดๆ ระหว่าง ลงใน Q${\displaystyle \scriptstyle C_{rq}}$และ${\displaystyle \scriptstyle C_{pq}^{-}}$แทรก จุดตัดใดๆ ระหว่าง ลงใน Q${\displaystyle \scriptstyle C_{pq}^{+}}$และ${\displaystyle \scriptstyle C_{qs}}$pเป็นจุดยอดโวโรนอยใน${\displaystyle \scriptstyle *(V)}$ให้ p เป็นจุดตัดของ${\displaystyle \scriptstyle C_{qr}}$ทางด้านซ้ายและ${\displaystyle \scriptstyle C_{rs}}$ทางด้านขวา ให้${\displaystyle \scriptstyle C_{uq}}$เป็นเพื่อนบ้านทางซ้ายของ${\displaystyle \scriptstyle C_{qr}}$และ ปล่อยให้${\displaystyle \scriptstyle C_{sv}}$เป็นเพื่อนบ้านที่ดีของ${\displaystyle \scriptstyle C_{rs}}$ในT ถ้า${\displaystyle \scriptstyle q_{y}=s_{y}}$สร้าง รังสีขอบเขตใหม่${\displaystyle \scriptstyle C_{qs}^{0}}$มิฉะนั้น ถ้าpอยู่ทางขวาของค่าที่สูงกว่าระหว่างqและsให้ สร้าง${\displaystyle \scriptstyle C_{qs}^{+}}$มิฉะนั้นสร้าง${\displaystyle \scriptstyle C_{qs}^{-}}$ แทนที่endif${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$ด้วยการสร้างใหม่${\displaystyle \scriptstyle C_{qs}}$ในT ให้ลบ ส่วนที่ทับซ้อนกันทั้งหมดออกจากQ${\displaystyle \scriptstyle C_{uq}}$และ${\displaystyle \scriptstyle C_{qr}}$ ลบ จุดตัดใดๆ ระหว่าง Q ออกจากQ${\displaystyle \scriptstyle C_{rs}}$และ${\displaystyle \scriptstyle C_{sv}}$แทรก จุดตัดใดๆ ระหว่าง ลงใน Q${\displaystyle \scriptstyle C_{uq}}$และ${\displaystyle \scriptstyle C_{qs}}$แทรก จุดตัดใดๆ ระหว่าง ลงใน Q${\displaystyle \scriptstyle C_{qs}}$และ${\displaystyle \scriptstyle C_{sv}}$ บันทึกpเป็นจุดสูงสุดของ${\displaystyle \scriptstyle C_{qr}}$และ${\displaystyle \scriptstyle C_{rs}}$และฐานของ${\displaystyle \scriptstyle C_{qs}}$ ส่งออกส่วนขอบเขต${\displaystyle \scriptstyle C_{qr}}$และ${\displaystyle \scriptstyle C_{rs}}$endcase endwhile ส่งออกรังสีขอบเขตที่เหลือในT

ตามที่ Fortune อธิบายไว้ในเอกสารอ้างอิง^{[ 1 ]}เวอร์ชันที่แก้ไขของอัลกอริทึมเส้นกวาดสามารถใช้สร้างแผนภาพ Voronoi ที่ถ่วงน้ำหนัก แบบบวกได้ โดยที่ระยะทางไปยังแต่ละไซต์จะถูกชดเชยด้วยน้ำหนักของไซต์ ซึ่งอาจมองได้ว่าเป็นแผนภาพ Voronoi ของชุดดิสก์ที่มีจุดศูนย์กลางอยู่ที่ไซต์และมีรัศมีเท่ากับน้ำหนักของไซต์ พบว่าอัลกอริทึมมี${\displaystyle O(n\log(n))}$ความซับซ้อนของเวลาโดยที่ n คือจำนวนไซต์ตามอ้างอิง^{[ 1 ]}

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