Đại Học Quốc Gia Thành Phố Hồ Chí Minh
Trường Đại Học Bách Khoa

MAI THÁI SƠN

THIẾT KẾ GIẢI THUẬT
TÍNH GIẢN ĐỒ VORONOI TRONG
MẶT PHẲNG
Chuyên ngành: Khoa học máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 7 năm 2007


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : TS. Lê Ngọc Minh.............................................

Cán bộ chấm nhận xét 1 : TS. Phan Đạt Phúc...................................................

Cán bộ chấm nhận xét 2 : TS. Nguyễn Văn Minh Mẫn ....................................

Luận văn thạc sĩ được bảo vệ tại
HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . 07 . tháng . 09 . năm . 2007 .


Lời cảm ơn

Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến TS. Lê Ngọc Minh người đã tận
tình hướng dẫn tơi trong suốt q trình từ đại học tới cao học và tạo mọi điều kiện để tơi
có thể hồn thành luận văn này.
Tơi cũng xin cảm ơn gia đình đã động viên và tạo mọi điều kiện tốt nhất để tơi có thể tiếp
tục theo đuổi việc học tập nghiên cứu.
Cuối cùng, tôi cũng xin gởi lời cảm ơn tới Prof. Frank Aurenhammer, Takashi Ohyama,
Ths. Bùi Trọng Hiếu và Ths. Nguyễn Văn Diêu những người đã nhiệt tình giúp đỡ và cho
tơi những ý kiến quý báu trong suốt quá trình học tập và thực hiện luận văn.


Tóm tắt
Trong đề tài này, ta tiến hành nghiên cứu mở rộng giản đồ Voronoi dựa trên hàm khoảng
cách convex theo hướng thêm trọng số vào cho các site. Giản đồ Voronoi kết quả ta gọi là
multiplicatively weighted convex distance function Voronoi diagram (MWCD). Đề tài
tiến hành khảo sát các tính chất và đưa ra các giải thuật tính MWCD trong mặt phẳng.
Ngoài ra, đề tài cũng chú trọng tới việc giải quyết một số vấn đề liên quan như vấn đề xác
định vị trí điểm,... Chương trình được xây dựng có khả năng tương tác tốt với người sử
dụng nhằm phục vụ cho công tác nghiên cứu và giảng dạy. Đồng thời một framework
tính giản đồ Voronoi cũng được xây dựng cho phép người dùng xây dựng các loại giản
đồ Voronoi khác nhau một cách dễ dàng.


Mục lục
Chương 1: Giới thiệu vấn đề ............................................................................................ 1
Chương 2: Cơ sở lý thuyết................................................................................................ 2
2.1 Cơ sở toán học ......................................................................................................... 2
2.1.1 Không gian Metric.......................................................................................... 2
2.1.2 Không gian định chuẩn .................................................................................. 2
2.1.3 Khơng gian Topo............................................................................................ 3
2.2 Hình học tính tốn ................................................................................................... 3

Chương 3: Tổng quan về giản đồ Voronoi trong mặt phẳng ........................................ 5
3.1 Định nghĩa và đặc điểm .......................................................................................... 5
3.2 Quan hệ với không gian 3 chiều.............................................................................. 6
3.3 Giải thuật tính giản đồ Voronoi và phân tam giác Delaunay .................................. 6
3.3.1 Chận dưới cho giải thuật tính giản đồ Voronoi .............................................. 6
3.3.2 Giải thuật Straightforward.............................................................................. 6
3.3.3 Giải thuật Incremental .................................................................................... 6
3.3.4 Phương pháp Edge-flipping............................................................................ 7
3.3.5 Phương pháp Divide and Conquer ................................................................. 7
3.3.6 Phương pháp Sweep-Plane............................................................................. 7
3.3.7 Phương pháp Convex Hull ............................................................................. 8
3.4 Giản đồ Voronoi tổng quát ...................................................................................... 8
3.4.1 Định nghĩa cho giản đồ Voronoi tổng quát .................................................... 8
3.4.2 Các dạng giản đồ Voronoi ............................................................................. 8
Chương 4: Ứng dụng của giản đồ Voronoi ................................................................... 10
Chương 5: Multiplicatively Weighted Convex Distance Function Voronoi Diagram
trong mặt phẳng................................................................................................... 13
5.1 Một số tính chất của Convex distance................................................................... 14
5.2 Một số định lý quan trọng ..................................................................................... 21
5.3 Định nghĩa cho MWCD ........................................................................................ 23
5.4 Convex distance function trong trường hợp tổng quát.......................................... 26
5.4.1 Bisector của hai site...................................................................................... 26
5.4.2 Bisector của ba site....................................................................................... 48
5.4.3 Giản đồ Voronoi ........................................................................................... 70
5.5 Euclidean Weighted Distance ............................................................................... 79
5.5.1 Bisector của hai site...................................................................................... 79
5.5.2 Bisector của ba site....................................................................................... 80
5.5.3 Giản đồ Voronoi ........................................................................................... 81
5.6 Polygonal Convex Distance function .................................................................... 82
5.6.1 Bisector của hai site...................................................................................... 82

5.6.2 Bisector của ba site....................................................................................... 87
5.6.3 Giản đồ Voronoi ........................................................................................... 89
5.6.5 Tính tốn bisector giữa hai site .................................................................... 90
5.6.6 Tính tốn bisector của ba site ....................................................................... 98
5.7 Các tập lồi nhẵn và ngặt ........................................................................................ 99
5.7.1 Bisector của hai site...................................................................................... 99
5.7.2 Bisector của ba site....................................................................................... 99
5.7.3 Giản đồ Voronoi ......................................................................................... 100
Chương 6: Giải thuật tính giản đồ Voronoi................................................................ 101


6.1 Cấu trúc dữ liệu tổng quát ................................................................................... 102
6.1.1 Cấu trúc dữ liệu cho giản đồ tổng quát....................................................... 102
6.1.2 Đồ thị Voronoi............................................................................................ 103
6.1.3 Các cấu trúc dữ liệu hỗ trợ ......................................................................... 106
6.2 Giải thuật raster trong tính giản đồ Voronoi ....................................................... 109
6.3 Giải thuật Straight-Forward................................................................................. 115
6.4 Giải thuật Incremental ......................................................................................... 116
6.5 Multiplicatively Weighted Voronoi Diagram ..................................................... 119
6.6 MultiplicativelyWeighted Polygonal Convex Distance Voronoi Diagram......... 131
6.7 Point Location ..................................................................................................... 138
6.7.1 Giải thuật Brute-Force................................................................................ 138
6.7.2 Đồ thị Voronoi............................................................................................ 138
6.7.3 Slab................................................................................................................... 139
6.7.4 Point location trên MWVD .............................................................................. 144
6.7.5 Point location trên MWCD............................................................................... 147
Chương 7: Chương trình .............................................................................................. 150
7.1 Giới thiệu chương trình ....................................................................................... 150
7.2 Thư viện LEDA................................................................................................... 151
7.3 Framework tính giản đồ Voronoi ........................................................................ 152

7.3.1 Các abstract class cho framework .............................................................. 153
7.3.2 Các handle class ......................................................................................... 157
7.4 Mở rộng các nghiên cứu...................................................................................... 158
Chương 8: Kết luận ....................................................................................................... 159


Danh mục hình
Hình 2.2.1: Star shaped.............................................................................................................3
Hình 3.1.1: Giản đồ Voronoi và phân tam giác Delaunay........................................................5
Hình 3.4.2.1: Additively weighted Voronoi diagrams trong mặt phẳng dưới khoảng cách
Euclid. Các đường tròn chỉ trọng số tương ứng của mỗi site....................................................8
Hình 4.1: Định tuyến cho trường học bằng giản đồ Voronoi thơng thường...........................10
Hình 4.2: Định tuyến cho trường học bằng cách sử dụng multiplicatively weighted VD.
Trong đó mỗi trường học được gán trọng số theo quy mơ của trường. ..................................10
Hình 4.3: Di chuyển robot từ s tới t qua các vật cản sử dụng giản đồ Voronoi. ....................11
Hình 5.1.1: Convex distance giữa hai điểm p và q với tập C cho trước.................................13
Hình 5.1.2: Tính chất metric của convex distance function. ..................................................14
Hình 5.1.3: Dịch chuyển p và q bởi một vector v , dC(p, q) khơng đổi..................................14
Hình 5.1.4: D là ảnh của C qua phép đối xứng tâm................................................................15
Hình 5.1.4: D là ảnh của C qua phép đối xứng tâm. D và C mở rộng với cùng một tỉ lệ dC(p,
q) thì dC(p, q)C + p chứa q và dC(p, q)D + q chứa p. ..............................................................15
Hình 5.1.5: Thay đổi C theo một tỉ lệ k. .................................................................................16
Hình 5.1.6: Đường trịn ngoại tiếp theo convex distance function.........................................17
Hình 5.1.7: Phép chiếu trung tâm và foot point x’..................................................................17
Hình 5.1.8: Tính chất ba điểm thẳng hàng..............................................................................18
Hình 5.1.9: Đường giới hạn trên (U) và dưới (L) của tập lồi. ................................................18
Hình 5.1.10: Điểm trái nhất (Lm) và phải nhất (Rm)................................................................19
Hình 5.1.9: Unit circle cho L1, L2 và L∞ metric trong mặt phẳng R2. .....................................19
Hình 5.2.1: Định lý Desargue. ................................................................................................20
Hình 5.2.2: Định lý Euler. ......................................................................................................21

Hình 5.3.1: Tịnh tiến C và mở rộng theo tỉ lệ wp cho mọi site p thuộc S. ..............................23
Hình 5.3.1: Giản đồ Voronoi với convex distance thơng thường và có trọng số ...................24
Hình 5.4.1.1: Khảo sát hai site p và q với tập lồi Cp và Cq. ...................................................25
Hình 5.4.1.2: Điểm x trên bisector của hai site p và q............................................................26
Hình 5.4.1.3: Bisector giữa p, q trong trường hợp trọng số bằng nhau. .................................27
Hình 5.4.1.4: Bisector của hai site p, q trong trường hợp suy biến (bên trái – bisector chứa
một vùng, bên phải – bisector chứa hai vùng).........................................................................28
Hình 5.4.1.5: Chosen bisector của hai site p, q (trái – lấy độ ưu tiên theo tọa độ, phải – lấy
theo đường phân giác). ............................................................................................................29
Hình 5.4.1.6: Bisector giữa hai site p, q với trọng số bằng nhau trong một vài trường hợp
được khảo sát...........................................................................................................................30
Hình 5.4.1.7: Giao của các tia px p , py p với các tia qyq , qxq ............................................31
Hình 5.4.1.8: Đường thẳng pq chứa hai điểm thuộc bisector của hai site p và q. ..................33
Hình 5.4.1.9: Tia px p sẽ khơng chứa điểm nào hoặc chứa một hoặc hai điểm thuộc bisector
hoặc chứa một đoạn thẳng thuộc bisector. ..............................................................................34
Hình 5.4.1.10: Bisector của hai site p và q sẽ nằm trong vùng FF và FB giới hạn bởi hai tia
ppa và ppb .............................................................................................................................34
Hình 5.4.1.11: Tia qxq chứa một và chỉ một điểm thuộc bisector của p và q........................35
Hình 5.4.1.12: Bisector giữa hai site p, q là đường cong kín cùng dạng với ∂C và bao quanh
site có trọng số nhỏ hơn là site q. ............................................................................................36


Hình 5.4.1.13: Bisector giữa hai site p, q với trọng số khác nhau trong một vài trường hợp
được khảo sát...........................................................................................................................37
Hình 5.4.1.14: Vùng của site q có dạng star-shaped. .............................................................38
Hình 5.4.1.15: Trường hợp bisector mới cắt hay nằm ngoài bisector cũ. ..............................39
Hình 5.4.1.16: Khi tăng trọng số của site p, bisector mới sẽ nằm trong bisector cũ. Kết quả
được khảo sát trên convex set là đường trịn. ..........................................................................40
Hình 5.4.1.17: Dịch chuyển site q theo chiều của vector E . .................................................40
Hình 5.4.1.18: Khi dịch chuyển site q theo phương pq. .........................................................42

Hình 5.4.1.19: Khi dịch chuyển site q, bisector mới sẽ tỉ lệ với bisector cũ. Các khảo sát
được thực hiện trên một số convex set đều cho kết quả phù hợp............................................43
Hình 5.4.1.20: Quay site q quanh site p. Các khảo sát được thực hiện trên một số convex set
cho thấy các dạng khác nhau của bisector...............................................................................44
Hình 5.4.1.21: Bisector của hai site p và q khơng lồi.............................................................45
Hình 5.4.1.22: Các kết quả khảo sát trên một số convex set cho thấy bisector có thể là biên
của tập khơng lồi. ....................................................................................................................46
Hình 5.4.2.1: Khảo sát bisector của ba site p, q, r. .................................................................47
Hình 5.4.1.2: Các trường hợp xảy ra khi tính bisector của ba điểm. ......................................48
Hình 5.4.2.2: Hai đường tròn ngoại tiếp giao nhau tại tối đa hai điểm. .................................49
Hình 5.4.2.3: Bisector của ba site p, q, r trong mặt phẳng. ....................................................50
Hình 5.4.2.4: Trong trường hợp tập lồi là hình thoi tâm là tâm hình thoi như trên. Ba site p,
q, r không thẳng hàng nhưng BmC(p,q,r) vẫn rỗng. .................................................................51
Hình 5.4.2.5: Bisector của ba site trong một số trường hợp được khảo sát............................51
Hình 5.4.2.6: Bisector của site trong trường hợp suy biến được khảo sát (màu đen – vùng
bisector của hai site, màu đỏ - bisector của ba site). ...............................................................52
Hình 5.4.2.7: Chosen bisector của ba site thẳng hàng. ...........................................................53
Hình 5.4.2.8: Trường hợp suy biến trong đó chosen bisector là một tia. ...............................54
Hình 5.4.2.9: Khi chosen bisector là tia phân giác của góc suy biến. ....................................55
Hình 5.4.2.10: Chosen bisector (theo phân giác) của ba site thẳng hàng. ..............................56
Hình 5.4.2.11: Khi chosen bisector là tia phân giác của góc suy biến. Bisector của ba site
khơng chứa nhiều hơn một điểm. ............................................................................................56
Hình 5.4.2.12: Bisector ba site trong trường hợp đường cong đường cong lấy theo chosen
bisector trong một vài trường hợp được khảo sát....................................................................57
Hình 5.4.2.13: Bisector của ba site có thể khơng có hoặc có nhiều điểm. .............................58
Hình 5.4.2.14: Bisector của ba site có thể chứa các đoạn thẳng hay các cung trong trường
hợp xảy ra suy biến..................................................................................................................59
Hình 5.4.2.15: Dù không xảy ra suy biến, bisector của ba site p, q, r vẫn có khả năng chứa
các cung...................................................................................................................................60
Hình 5.4.2.16: Một ví dụ khác cho trường hợp dù khơng suy biến, bisector của ba site p, q, r

vẫn chứa các cung, với p, q, r khơng thẳng hàng. ...................................................................61
Hình 5.4.2.17: Bisector của ba site chứa một điểm trong trường hợp xảy ra suy biến và sử
dụng chosen bisector. ..............................................................................................................61
Hình 5.4.2.18: Khi không sử dụng chosen bisector, BmC(p,q,r) không rỗng nhưng nếu sử
dụng chosen bisector kết quả là rỗng. .....................................................................................61
Hình 5.4.2.19: Bisector ba site trong trường hợp đường cong cung kín được khảo sát. ........62
Hình 5.4.2.20: Bisector của ba site khơng có hoặc có nhiều điểm. ........................................63
Hình 5.4.2.21: Bisector của ba site p, q, r chứa một cung......................................................64
Hình 5.4.2.22: Bisector ba điểm trong trường hợp cung kín giao cung kín khảo sát. ............64
Hình 5.4.2.23: Mâu thuẫn trong sử dụng chosen bisector? ....................................................65


Hình 5.4.2.24: Khi bisector ba site chứa một cung.................................................................66
Hình 5.4.2.25: Trong trường hợp cung là đoạn thẳng. ...........................................................66
Hình 5.4.2.26: Một số kết quả khảo sát bisector của ba site trong trường hợp trọng số khác
nhau. ........................................................................................................................................68
Hình 5.4.3.1: Mọi điểm x trong mặt phẳng sẽ thuộc về VmC(S) hoặc VRmC(p). ......................70
Hình 5.4.3.2: Vùng Voronoi của hai site p, q có điểm chung?...............................................70
Hình 5.4.3.3: Vùng của site q và r là hai hole trong vùng của site p......................................71
Hình 5.4.3.4: Vùng của site p khơng liên thơng. ....................................................................72
Hình 5.4.3.5: Giản đồ Voronoi được khảo sát trên một số tập lồi khác nhau. Kết quả cho thấy
vùng Voronoi của site có thể chứa các hole và khơng liên thơng. ..........................................73
Hình 5.4.3.6: Các đỉnh và cạnh Voronoi được khảo sát trong một vài trường hợp................74
Hình 5.4.3.7: Khơng tồn tại đường trịn ngoại tiếp cho ba site p, q, r. ...................................75
Hình 5.4.3.8: Trường hợp xấu nhất xảy ra khi tính số đỉnh và cạnh. .....................................76
Hình 5.4.3.9: Một vài kết quả khảo sát giản đồ Voronoi........................................................77
Hình 5.5.1.1: Đường trịn Apollonius.....................................................................................79
Hình 5.5.2.1: Các trường hợp giao nhau của bisector của ba site. .........................................79
Hình 5.5.3.1: Giản đồ Voronoi. ..............................................................................................80
Hình 5.6.1.1: Đoạn thẳng xy thuộc bisector của hai site p, q..................................................81

Hình 5.6.1.2: Bisector BmC(p,q) được chia thành ba phần. .....................................................82
Hình 5.6.1.3: Khảo sát bisector trong khoảng FF ngoại trừ hai support line. ........................83
Hình 5.6.1.4: Bisector BmC(p,q) trong FF khi trọng số bằng nhau. ........................................84
Hình 5.6.1.5: Số đỉnh trên bisector trường hợp trọng số khác nhau.......................................84
Hình 5.6.1.6: Bisector của hai site..........................................................................................85
Hình 5.6.1.1: Ví dụ cho trường hợp hai polygon giao nhau tại O(k2) điểm. ..........................86
Hình 5.6.2.3: Bisector của ba site, a và b – đường cong và cung kín giao nhau tại hai đoạn
thẳng và chosen bisector, c và d – đường cong đường cong giao nhau tại một tia và chosen
bisector, e và f – hai cung kín giao nhau tại hai đoạn thẳng và chosen bisector, g và h – giao
tại khơng hay nhiều điểm. .......................................................................................................87
Hình 5.6.3.1: Giản đồ Voronoi. ..............................................................................................88
Hình 5.6.4.1: Sweep-line nằm trên đường thẳng pq. ..............................................................89
Hình 5.6.4.2: Sweep-line nằm trên đường giới hạn của Cq. ...................................................90
Hình 5.6.4.3: Sweep-line không trùng với pq và không trùng với đường giới hạn. ..............90
Hình 5.6.4.4: Bisector BmC(p,q) được chia thành ba phần. .....................................................90
Hình 5.6.4.5: Tính dmC(p,q). ...................................................................................................90
Hình 5.6.4.6: Tính foot point của vector x trên biên ∂C. ........................................................96
Hình 5.7.1.1:Bisector với tập lồi là đường trịn. .....................................................................98
Hình 5.7.2.1: Bisector của ba site với tập lồi có biên là đường trịn. .....................................98
Hình 5.7.3.1: Giản đồ Voronoi với tập lồi có biên là đường trịn...........................................99
Hình 6.4.1: Đồ thị Voronoi với MWCD...............................................................................104
Hình 6.4.2: Đồ thị Voronoi với MWVD. .............................................................................104
Hình 6.2.1: Giải thuật raster. ................................................................................................108
Hình 6.2.2: Một số ví dụ cho giải thuật raster. .....................................................................112
Hình 6.4.1: Giản đồ Voronoi trên S’ (hình a), chèn thêm site p (hình b) và giản đồ Voronoi
sau khi tính tốn lại (hình c). .................................................................................................115
Hình 6.5.1: Một số phần mềm vẽ MWVD (Gambini và Voronoi).......................................118
Hình 6.5.2: Quy ước cho chiều của bisector.........................................................................119
Hình 6.5.3: Trường hợp đoạn thẳng và đường thẳng. ..........................................................120
Hình 6.5.4: Trường hợp cung và đường thẳng. ....................................................................121



Hình 6.5.5: Trường hợp đường trịn và đường thẳng. ..........................................................121
Hình 6.5.6: Trường hợp đoạn thẳng và đường trịn..............................................................122
Hình 6.5.7: Trường hợp cung và đường trịn........................................................................123
Hình 6.5.8: Trường hợp đường trịn và đường trịn..............................................................123
Hình 6.5.9: Kết quả của phép clip và sắp xếp giao điểm theo thứ tự trên bisector. .............125
Hình 6.6.1: Phân vùng trong trường hợp các site có trọng số bằng nhau.............................131
Hình 6.6.2: Giao của hai polygon.........................................................................................133
Hình 6.7.2.1: Đồ thị Voronoi trên point site thơng thường. .................................................138
Hình 6.7.3.1: Slab trên đồ thị G............................................................................................138
Hình 6.7.4.1: Giản đồ Voronoi (hình a) và đồ thị tìm kiếm sau khi tách các cạnh thành good
arc (hình b). ...........................................................................................................................144
Hình 6.7.4.2: Cấu trúc slab và vấn đề định vị trí cho điểm q. ..............................................145
Hình 6.7.4.1: Giản đồ Voronoi (hình a) và đồ thị tìm kiếm sau khi tách các cạnh thành các
đoạn thẳng (hình b)................................................................................................................146
Hình 6.7.5.2: Cấu trúc slab và vấn đề định vị trí cho điểm q. ..............................................147
Hình 7.1.1: Giao diện chương trình. .....................................................................................150
Hình 7.4.1: Giản đồ Voronoi với trọng số nhân và trọng số cộng dựa trên convex distance
function..................................................................................................................................157


Danh mục bảng
Bảng 6.2.1: Khảo sát giải thuật Raster trên Euclidean point site. .........................................113
Bảng 6.2.2: Khảo sát giải thuật raster trên MWVD. .............................................................113
Bảng 6.2.3: Khảo sát giải thuật raster trên MWCD. .............................................................113
Bảng 6.5.1: So sánh giải thuật straight-forward và incremental. ..........................................127
Bảng 6.5.2: Đo đạc thời gian insert site và thời gian tính tốn lại giản đồ. ..........................127
Bảng 6.5.3: Khảo sát ảnh hưởng của việc sắp xếp các site...................................................128
Bảng 6.5.4: Thời gian tính tốn các thành phần....................................................................128

Bảng 6.5.5: So sánh với GAMBINI. .....................................................................................128
Bảng 6.5.1: So sánh giải thuật straight-forward và incremental. ..........................................135
Bảng 6.5.2: Đo đạc thời gian insert site và thời gian tính tốn lại giản đồ. ..........................135
Bảng 6.5.3: Khảo sát ảnh hưởng của việc sắp xếp các site...................................................136
Bảng 6.5.4: Thời gian tính tốn các thành phần....................................................................136
Bảng 6.7.4.1: So sánh thời gian query giải thuật brute-force và slab trên MWVD. .............145
Bảng 6.7.5.1: So sánh thời gian query giải thuật brute-force và slab trên MWCD. .............148


Chương 1: Giới thiệu vấn đề
Cho một không gian M, một tập S các site p cho trước thuộc M và một định nghĩa về sự
ảnh hưởng của p lên một điểm x bất kỳ thuộc M. Một vùng của p sẽ chứa đựng tất cả các
điểm x thuộc M sao cho ảnh hưởng của p lên x là lớn hơn ảnh hưởng của tất cả các điểm
còn lại trong S. Cấu trúc thu được gọi là giản đồ Voronoi hay khảm Dirichlet được giới
thiệu đầu tiên bởi hai nhà toán học Dirichlet và Voronoi với M là một mặt phẳng và hàm
ảnh hưởng được xác định bằng khoảng cách Euclid giữa hai điểm trong mặt phẳng.
Voronoi cũng là người đầu tiên tìm hiểu về một cấu trúc dual với cấu trúc được nêu ở
trên, trong đó hai site bất kỳ sẽ có cạnh nối nếu vùng của chúng có cạnh chung. Cấu trúc
này về sau được Delaunay khảo sát và định nghĩa và được đặt tên là khảm Delaunay hay
phân tam giác Delaunay.
Giản đồ Voronoi (VD) được ứng dụng rất rộng rãi và giải quyết rất nhiều vấn đề
trong nhiều ngành khoa học như: vật lý, sinh vật học, hóa học, địa lý, khí tượng học cũng
như trong khoa học máy tính. Rất nhiều các nghiên cứu về giản đồ Voronoi đã được tiến
hành và cho các kết quả rất phong phú.
Trong đề tài này, ta tiến hành khảo sát các đặc tính và xây dựng giải thuật tính giản đồ
Voronoi trong mặt phẳng dựa trên hàm ảnh hưởng là convex distance function với trọng
số khác nhau cho mỗi site. Giản đồ kết quả ta đặt tên là multiplicatively weighted convex
distance function Voronoi diagram (MWCD).
Trong phần 2, ta sẽ giới thiệu cơ sở lý thuyết của giản đồ Voronoi. Phần 3 trình bày
khái quát về giản đồ Voronoi và phân tam giác Delaunay, khảo sát định nghĩa và một vài

đặc tính của chúng trong mặt phẳng dựa trên khoảng cách Euclid làm cơ sở cho các vấn
đề được trình bày phía sau, giới thiệu các giải thuật thơng dụng trong tính tốn giản đồ
Voronoi và cấu trúc song sinh của nó, phân tam giác Delaunay, cuối cùng ta sẽ điểm qua
các nghiên cứu mở rộng giản đồ Voronoi đã được cơng bố. Phần 4 ta sẽ trình bày về một
số ứng dụng của giản đồ Voronoi. Phần 5 ta sẽ trình bày về lý thuyết của MWCD. Phần 6
trình bày giải thuật xây dựng giản đồ Voronoi, các kết quả đo đạc, đánh giá. Phần 7 ta
giới thiệu chương trình và một vài hướng nghiên cứu tiếp theo. Phần 8 ta tổng kết đánh
giá lại vấn đề.

1


Chương 2: Cơ sở lý thuyết
Trong phần này ta sẽ trình bày một số kiến thức cơ bản trong tốn học và khoa học máy
tính có liên quan.

2.1 Cơ sở tốn học
Trong phần này ta sẽ trình bày một số khái niệm cơ bản về metric và không gian định
chuẩn. Chi tiết có thể tham khảo trong [6] và [43].

2.1.1 Không gian Metric
Định nghĩa 2.1.1.1 Metric và không gian metric. Cho X là một tập. Một metric trên X là
một hàm d : X × X → R thỏa mãn các tính chất sau:
1) d(x, y) ≥ 0, d(x, y) = 0 ↔ x = y
2) d(x, y) = d(y, x)
3) d(x, z) ≤ d(x, y) + d(y, z) (tính chất tam giác)
với mọi x, y, z ∈ X.
Không gian metric X = (X, d) là một tập hợp X cùng với một metric d trên nó.
Ví dụ: khơng gian Euclid là một khơng gian metric do nó thỏa các tính chất metric với
hàm khoảng cách là hàm Euclid và tập hợp X là R2.


2.1.2 Không gian định chuẩn
Định nghĩa 2.1.2.1 Không gian định chuẩn. Cho E là một K - không gian vector. Một
chuẩn (norm) trên E là một hàm || . || : E → R thỏa mãn các điều kiện sau với mọi x, y ∈
E, mọi k ∈ K.
1) || x || ≥ 0, || x || = 0 ↔ x = 0
2) || kx || = |k| || x || (tính thuần nhất của chuẩn)
3) || x + y || ≤ || x || + || y || (bất đẳng thức tam giác)
Một không gian định chuẩn E = (E, || . ||)là một không gian vector cùng với một chuẩn
trên nó.
Ta quan tâm tới không gian Euclid (R2, || . ||) trong mặt phẳng R2, với || . || là chuẩn Euclid
được định nghĩa như sau:
|| . || : R2 → R sao cho || (x, y) || = x 2 + y 2
Dễ thấy với định nghĩa trên || . || là một chuẩn.
Không gian Euclid bậc n (Rn, || . ||) là khơng gian vector Rn trong đó chuẩn được định
nghĩa như sau:

2


|| . || : Rn → R sao cho || (x1, x2,..,xn) || =

n

∑x
i =1

2
i


Định lý 2.1.2.1 Nếu || . || là một chuẩn trên E thì d(x, y) = || x – y || là một metric trên E.
Một không gian định chuẩn là không gian metric với metric được sinh ra bởi chuẩn.
Không gian định chuẩn là một trường hợp riêng của không gian metric.

2.1.3 Không gian Topo
Định nghĩa 2.1.3.1 Không gian Topo. Cho một tập X. Một họ D các tập con của X gọi là một
Topo trên X nếu thỏa các tính chất:
1) ∅ ∈ D, X ∈ D
2) D kín với phép hơp bất kỳ hay hợp của một số bất kỳ (hữu hạn hay vơ hạn) tập hợp
thuộc D thì cũng thuộc D.
3) D kín với phép giao hữu hạn hay giao của một số hữu hạn các tập thuộc D thì cũng
thuộc D.
Khơng gian topo X = (X, D) là một tập X cùng với một topo D trên nó.
Nếu X là một khơng gian Topo thì các tập U ∈ D là các tập mở, các phần tử của X gọi là các
điểm.
Như vậy cho một Topo trên tập hợp X tức là quy định các tập con nào của X được coi là tập
mở và việc quy định này phải thỏa các tính chất 1, 2, 3 nêu trên.
Các khơng gian metric là khơng gian Topo, Topo trên nó là Topo sinh bởi metric. Không
gian định chuẩn cũng là không gian Topo.
Định nghĩa 2.1.3.1 Ánh xạ liên tục. Một ánh xạ f từ X vào Y được gọi là liên tục tại xo nếu
với mọi lân cận Uyo của điểm yo = f(xo) đều tồn tại một lân cận Vxo của điểm xo sao cho f(Vxo)
⊂ Uyo, nghĩa là x ∈ Vxo → f(x) ∈ Uyo. Ánh xạ f gọi là liên tục nếu nó liên tục tại mọi x ∈ X.

2.2 Hình học tính tốn
Ta giới thiệu một số khái niệm cơ bản của hình học tính tốn.
Định nghĩa 2.2.1 Đa giác (polygon) là một dãy các đoạn thẳng trong đó điểm đầu của
đoạn thẳng này là điểm cuối của đoạn thẳng kia và ngược lại.
Đa giác lồi (convex) nếu mọi đỉnh của đa giác đều nằm trong cùng nửa mặt phẳng chứa
một cạnh bất kỳ của đa giác, ngược lại đa giác là không lồi (non-convex, concave).
Định nghĩa 2.2.2 Một đồ thị (graph) G = (V, E) trong đó V là tập các đỉnh (vertex), E là

tập các cạnh (edge) được gọi là phẳng (planar) nếu nó có thể đặt vào trong mặt phẳng sao
cho khơng có cạnh nào cắt nhau (sự cắt nhau của các cạnh là sự cắt nhau của các đường
hay cung biểu diễn chúng tại một điểm không phải là điểm mút chung của chúng).

3


Định lý 2.2.1 Định lý Euler. G là một đồ thị đơn, phẳng, liên thơng có e cạnh và v đỉnh.
Gọi r là số miền trong biểu diễn phẳng của G. Khi đó r = e – v + 2.
Định nghĩa 2.2.3 Star-shaped. Một vùng gọi là star-shaped với một điểm p nếu với mọi
điểm q thuộc vùng đó, mọi điểm thuộc đoạn thẳng pq đều nằm trong vùng.
Hay
∀q ∈ C , 0 ≤ λ ≤ 1: λ p + (1-λ )q ∈ C

p

p

Star-shaped

Not star-shaped
Hình 2.2.1: Star shaped.

4


Chương 3: Tổng quan về giản đồ Voronoi trong
mặt phẳng
Tổng quan về giản đồ Voronoi có thể tham khảo trong các tài liệu của Aurenhammer [1,
2], Okabe et al. [35], Marina [33] và Lawson [24].


3.1 Định nghĩa và đặc điểm
Trong mặt phẳng tọa độ cho một tập điểm S, với mỗi điểm thuộc S ta gọi là một site. Với
hai điểm x và y thuộc mặt phẳng, ký hiệu d(x, y) là khoảng cách Euclid giữa hai điểm x
và y. Ký hiệu xy là đoạn thẳng hai đầu là x và y. Ký hiệu xy là vector có gốc là x và đầu
là y. Ký hiệu A là bao đóng (closure) của tập A.
Định nghĩa 3.1.1 [1] Bisector của hai site p, q trong mặt phẳng,
B ( p, q) = {x | d ( p, x) = d (q, x)}
B(p,q) gọi là bisector của p và q. Trong trường hợp này B(p,q) là đường trung trực của
pq .
Gọi D(p,q) là một nửa mặt phẳng có bờ là B(p,q) chứa p như vậy D(p,q) chứa các điểm
gần p hơn q.
D( p, q ) = {x | d ( p, x) < d (q, x)}
Gọi VR(p,S) là vùng Voronoi (Voronoi region) của p với tập S. VR(p,S) chứa các điểm
gần p hơn bất kỳ điểm nào khác trong tập S. Ta có thể ký hiệu đơn giản là VR(p).
VR( p, S ) = ∩ D( p, q )
q∈S , q ≠ p

Giản đồ Voronoi (Voronoi diagram) của S được định nghĩa như sau:
V ( S ) = ∪ VR( p, S ) ∩VR(q, S )
p , q∈S , p ≠ q

Các phân vùng của các site là các vùng lồi, các phân vùng của các site thì disjoint với
nhau. Biên chung của hai phân vùng là các cạnh Voronoi, điểm cuối của các cạnh
Voronoi được gọi là các đỉnh Voronoi. Các cạnh Voronoi có thể là cạnh hữu hạn hay
cạnh vơ hạn. Nếu gọi Γ là một đường cong khép kín (closed curve) bao xung quanh giản
đồ Voronoi và đủ lớn sao cho Γ chỉ giao với các cạnh vô hạn của giản đồ Voronoi. Khi
xem xét Γ theo thứ tự cùng hay ngược chiều kim đồng hồ ta cũng xác định được các đỉnh
của bao lồi (convex hull) của S theo thứ tự cùng hay ngược chiều kim đồng hồ. Giản đồ
Voronoi bị giới hạn trong cung kín Γ được gọi là giản đồ Voronoi hữu hạn (finite

Voronoi diagram) [1].
Định nghĩa 3.1.2 Khảm Delaunay (Delaunay tesselation) DT(S) được xây dựng bằng
cách nối hai site p và q thuộc S bằng một đoạn thẳng nếu tồn tại một đường tròn C đi qua
hai site p và q đồng thời C không chứa bất kỳ một site nào khác thuộc S ngoài p và q [1].

5


Hình 3.1.1: Giản đồ Voronoi và phân tam giác Delaunay.

3.2 Quan hệ với không gian 3 chiều
Giản đồ Voronoi và phân tam giác Delaunay trong mặt phẳng có thể thu được bằng cách
thực hiện các tính tốn trên khơng gian ba chiều và chiếu các kết quả thu được xuống mặt
phẳng. Chi tiết tham khảo trong [1] và [33].

3.3 Giải thuật tính giản đồ Voronoi và phân tam giác Delaunay
Marina [33] phân loại các giải thuật thành hai dạng tất định và ngẫu nhiên, đồng thời
cũng liệt kê các giải thuật thơng dụng tính giản đồ Voronoi như sau: straightforward,
incremental, edge flipping, divide and conquer, sweep plane, convex hull.

3.3.1 Chận dưới cho giải thuật tính giản đồ Voronoi
Aurenhammer [1] chỉ ra rằng, việc xây dựng giải thuật tính giản đồ Voronoi cũng như
cấu trúc song sinh của nó, phân tam giác Delaunay tốn thời gian chận dưới Ω(nlogn).

3.3.2 Giải thuật Straightforward
Giải thuật này dựa trên định nghĩa của giản đồ Voronoi (Định nghĩa 3.1.1). Với mỗi site
p, vùng Voronoi của nó được tính bằng cách tính giao của n–1 nửa mặt phẳng. Kết quả
thu được là giản đồ Voronoi trên tập S. Giải thuật có độ phức tạp thời gian O(n3) và là
giải thuật chậm nhất trong số các giải thuật để tính giản đồ Voronoi được biết.


3.3.3 Giải thuật Incremental
Giải thuật tăng dần (incremental) mặc dầu đơn giản nhưng lại là một trong những
phương pháp thông dụng nhất trong cả nghiên cứu lẫn thực nghiệm trên giản đồ Voronoi.
Trong phương pháp này ta khởi đầu với giản đồ Voronoi của 3 site. Tại mỗi bước ta sẽ
chỉnh sửa lại giản đồ Voronoi bằng cách bổ sung thêm một site vào cho tới khi tất cả các
site đều được đặt vào giản đồ. Phương pháp này được giới thiệu lần đầu tiên bởi Green
và Sibson [16]. Trong trường hợp xấu nhất độ phức tạp thời gian của giải thuật là O(n2)
mặc dù các kết quả đạt được có thể tốt hơn nếu thứ tự chèn các site vào giản đồ là hợp lý.
Các giải thuật tăng dần phân thành hai loại: xây dựng tăng dần (incremental construction)
và tìm kiếm tăng dần (incremental search).

6


Giải thuật xây dựng tăng dần, được giới thiệu bởi Guibas [17], thêm các site vào đồ
thị từng site một trong khi vẫn duy trì phân tam giác Delaunay. Khi một site được thêm
vào trong đồ thị, trước tiên tam giác chứa site được xác định bằng cách áp dụng giải thuật
CCW (counter clock wise), sau đó tiến hành hốn đổi đường chéo (diagonal swap) trên
các cạnh dựa trên kết quả kiểm tra của thủ tục INCIRCLE.
Giải thuật tìm kiếm tăng dần, giới thiệu bởi Dwyer [10], xây dựng đồ thị kết quả bằng
một tam giác cho mỗi lần, giải thuật bắt đầu với một tam giác Delaunay, sau đó thực hiện
phép hoán đổi đường chéo, nếu cần thiết, khi một tam giác mới được xem xét.
Độ phức tạp thời gian của hai loại giải thuật trên vào khoảng O(n2).
Một phương pháp khác được đưa ra bởi Watson [44], hơi khác một chút so với các
phương pháp nêu trên. Khi một tam giác mà đường trịn ngoại tiếp của nó chứa site mới
được thêm vào, tam giác đó sẽ bị xóa, và vùng khơng gian nó để lại, có dạng star-shaped,
sẽ được tái phân tam giác. Độ phức tạp thời gian của giải thuật này, trong trường hợp xấu
nhất là O(n2).

3.3.4 Phương pháp Edge-flipping

Phương pháp đảo cạnh (edge-flipping), thường đi kèm với phương pháp tăng dần trong
xây dựng phân tam giác Delaunay, được giới thiệu bởi Sibson [16] vào 1978 dùng trong
phân tam giác cho bao lồi. Sibson chứng minh rằng, phân tam giác cho bao lồi có thể
được chuyển đổi thành phân tam giác Delaunay bằng cách đảo đường chéo trong các tứ
giác theo tiêu chuẩn min-max trong mặt phẳng. Độ phức tạp thời gian của thuật toán là
O(n2).

3.3.5 Phương pháp Divide and Conquer
Phương pháp chia để trị (divide and conquer) là một phương pháp phổ biến trong tính
tốn giản đồ Voronoi cũng như phân tam giác Delaunay. Ý tưởng cơ bản của giải thuật
như sau, tập các site S sẽ được phân chia đệ quy thành tập các site nhỏ hơn sau đó giản
đồ Voronoi cho tập các site này sẽ được tính tốn sau đó các giản đồ Voronoi này sẽ
được trộn (merge) với nhau để tạo ra giản đồ Voronoi kết quả. Do bước merge hai đồ thị
kết quả tốn thời gian O(n), độ phức tạp thời gian cho phương pháp chia để trị vào khoảng
O(nlogn).
Giải thuật chia để trị được giới thiệu lần đầu tiên bởi Shamos and Hoey [41] để tính
tốn giản đồ Voronoi. Guibas and Stolfi [18] sử dụng giải thuật chia để trị trong tính tốn
phân tam giác Delaunay.

3.3.6 Phương pháp Sweep-Plane
Vào năm 1987, Fortune [12] đưa ra kĩ thuật quét (sweepline hay sweep-plane) để tính
tốn giản đồ Voronoi trong mặt phẳng. Theo đó, một đường thẳng gọi là đường thẳng
quét (sweepline) sẽ được dịch chuyển từ trái sang phải và lần lượt quét qua các site thuộc
S. Mỗi lần site được quét qua, một phần của giản đồ Voronoi kết quả được xây dựng.
Độ phức tạp thời gian của thuật toán là O(nlogn) và là một trong những thuật toán được
sử dụng rộng rãi nhất để tính giản đồ Voronoi.

7



3.3.7 Phương pháp Convex Hull
Phương pháp này dựa trên mối quan hệ giữa giản đồ Voronoi, phân tam giác Delaunay
đối với không gian 3 chiều. Một phép biến đổi T biến đổi tập các site S trong mặt phẳng
lên không gian 3 chiều. Từ việc tính tốn bao lồi trong không gian 3 chiều sẽ thu được đồ
thị kết quả trong khơng gian 2 chiều. Do việc tính tốn bao lồi trong khơng gian ba chiều
có tổn phí thời gian là O(nlogn) nên thời gian xây dựng giản đồ Voronoi cũng như phân
tam giác Delaunay cũng vào khoảng O(nlogn).

3.4 Giản đồ Voronoi tổng quát
Các nghiên cứu về mở rộng giản đồ Voronoi bắt đầu từ những năm 70 không chỉ dừng
lại trong việc mở rộng lên không gian 3 chiều và tổng qt hơn là khơng gian k-chiều mà
cịn mở rộng trên đối tượng là các site bất kỳ và metric bất kỳ.

3.4.1 Định nghĩa cho giản đồ Voronoi tổng quát
Cho một tập S các đối tượng bất kỳ trong khơng gian Rd. Giản đồ Voronoi tổng qt có
thể được định nghĩa như là sự phân chia không gian thành các vùng bao quanh một đối
tượng P sao cho với mọi điểm x trong không gian và nằm trong vùng của P thì khoảng
cách từ x tới P là nhỏ hơn khoảng cách từ x tới tất cả các đối tượng Q ≠ P trong S [33].
Định nghĩa 3.4.1.1 [33] Giản đồ Voronoi tổng quát (generalized Voronoi Diagram GVD) với một tập S các đối tượng trong không gian Rd là tập hợp các vùng Voronoi

VR ( P, S ) = {x | d ( P, x) ≤ d (Q, x), ∀Q ∈ S − {P}}
Trong đó d(P,x) là hàm khoảng cách giữa một điểm x bất kỳ thuộc không gian Rd với đối
tượng P thuộc tập đối tượng S.
Định nghĩa 3.4.1.2 [33] Phân tam giác Delaunay tổng quát (generalized Delaunay
triangulation – GDT) là cấu trúc song sinh của giản đồ Voronoi tống quát, được tạo thành
bằng cách nối hai site có vùng Voronoi kề nhau bằng một cạnh.

3.4.2 Các dạng giản đồ Voronoi
™ Giản đồ Voronoi trong không gian 3 chiều
Giản đồ Voronoi và phân tam giác Delaunay cũng có thể được mở rộng trong khơng gian

3 chiều và tổng quát hơn trong không gian n-chiều. Trong không gian 3 chiều, cho tập S
các site là các điểm bất kỳ trong không gian, một vùng Voronoi của một site thuộc S sẽ là
một convex polyhedron. Các giải thuật tính giản đồ Voronoi trong khơng gian 3 chiều có
độ phức tạp thời gian O(n2) [1].

™ Giản đồ Voronoi với trọng số

8


Giản đồ Voronoi với trọng số là giản đồ Voronoi trong đó mỗi site p sẽ được gán trọng
số w(p) tương ứng với nó. Khoảng cách từ một site p tới một điểm x bất kỳ sẽ được tính
dựa vào khoảng cách d(p,x) và trọng số w(p) tương ứng của p.
¾ Multiplicatively weighted distance function: d m ( p, x) = d ( p, x) / w( p )
¾ Additively weighted distance function: d a ( p, x) = d ( p, x) − w( p )
¾ Compoundly weighted distance function: d c ( p, x) = d ( p, x) / w1 ( p) − w 2 ( p)
¾ Power diagram: d p ( p, x) = pow( p, x) = d ( p, x) 2 − w( p)

Các giản đồ Voronoi dựa vào các hàm khoảng cách trên sẽ có tên tương ứng lần lượt là
multiplicatively weighted VD, additively weighted VD, compoundly weighted VD, power
diagram [33].

Hình 3.4.2.1: Additively weighted Voronoi diagrams trong mặt phẳng dưới
khoảng cách Euclid. Các đường tròn chỉ trọng số tương ứng của mỗi site.

™ Higher-order diagram
Higher-order Voronoi diagram được định nghĩa như sau: Cho tập các site S trong
không gian Rd và một số nguyên k trong khoảng từ 1 tới n – 1. Order-k Voronoi diagram
của S, ký hiệu Vk(S) là sự phân chia không gian thành các vùng sao cho mỗi điểm trong
cùng một vùng sẽ có k site gần nó nhất. Trong trường hợp đặc biệt k = n – 1, Vk(S) trở

thành furthest-site Voronoi diagram. Với mỗi site p thuộc S, region của p sẽ chứa các
điểm x sao cho khoảng cách từ p tới x là xa nhất [1].

™ Các dạng site tổng quát
Trong trường hợp này, các site trong không gian Rd không nhất thiết phải là các điểm mà
có thể được mở rộng với hình dạng bất kỳ, có thể là một đường thẳng, một đường trịn,
một polygon lồi,...

™ Các dạng khoảng cách tổng quát
Khoảng cách trong giản đồ Voronoi không nhất thiết phải là khoảng cách Euclid trong
không gian, trong trường hợp tổng quát, khoảng cách có thể là một hàm bất kỳ như
convex distance, nice metric,...

9


Chương 4: Ứng dụng của giản đồ Voronoi
Giản đồ Voronoi ứng dụng rộng rãi trong rất nhiều lãnh vực khác nhau từ tốn học, vật
lý, hóa học, sinh học, dự báo thời tiết, bản đồ, GIS,... Drysdale [9] liệt kê một vài lãnh
vực và các áp dụng của giản đồ Voronoi trong các lãnh vực đó như sau:
¾ Nhân loại học và cổ nhân loại học: xác định lãnh thổ, tầm ảnh hưởng của các bộ
lạc, phân vùng ảnh hưởng về tơn giáo, chính trị, qn sự,...
¾ Thiên văn học: phân vùng ảnh hưởng của các vì sao và thiên hà,...
¾ Sinh vật học, sinh thái học và lâm nghiệp: mơ hình và giám sát sự cạnh tranh sinh
tồn,...
¾ Bản đồ: khảo sát các vùng hoạt động, sự chồng lớp bản đồ,...
¾ Hóa học và tinh thể học: khảo sát các đặc tính của các tinh thể kim loại (“WignerSeitz regions”), mơ hình hóa các cấu trúc của hợp kim (“Domain of an atom”),...
¾ Địa lý: phân tích mẫu hay phân vùng dân cư trong đơ thị,...
¾ Khí tượng học: phân vùng lấy mẫu để đo lượng mưa theo từng thời kỳ, cho trước
các trạm đo (“Thiessen polygons”),...

¾ Robotics: kế hoạch tìm đường tránh các chướng ngại vật,...
¾ Khảo sát dữ liệu: phân vùng và lấy mẫu dữ liệu,...
Riêng trong Khoa học máy tính và Hình học tính tốn, giản đồ Voronoi cũng được áp
dụng để giải quyết nhiều vấn đề như:
¾ Knuth's Post Office Problem: cho trước hệ thống bưu điện, làm sao biết bưu điện
nào ở gần nhà mình nhất ?
¾ Closest Pair: cho trước một tập các điểm, xác định hai điểm gần nhau nhất.
¾ All Nearest Neighbors: cho trước một tập các điểm, tìm các điểm gần nhất cho
mỗi điểm.
¾ Euclid Minimum Spanning Tree: tìm cây phủ tối tiểu.
¾ Largest Empty Circle (Toxic Waste Dump Problem).
¾ Fixed Radius Near Neighbors: tìm tất cả cặp điểm mà khoảng cách gần hơn một
khoảng cách cho trước.
¾ All k Nearest Neighbors: tìm k điểm gần nhất cho mỗi điểm.
Trong hệ thống thông tin địa lý GIS, giản đồ Voronoi cũng được ứng dụng rất rộng rãi.
Chi tiết về ứng dụng giản đồ Voronoi trong GIS có thể được tham khảo tại [91].
Phần dưới đây ta sẽ xem xét một vài ứng dụng của giản đồ Voronoi.

™ Phân vùng định tuyến cho trường học
Bài toán đặt ra như sau, cho tập các trường học của UK, xác định những học sinh trong
tuyến sẽ được chuyển tới học tại trường đó [37]. Peace sử dụng giản đồ Voronoi thông
thường và multiplicatively weighted Voronoi cho việc định tuyến học sinh.

10


Hình 4.1: Định tuyến cho trường học bằng giản đồ Voronoi thơng thường [37].

Hình 4.2: Định tuyến cho trường học bằng cách sử dụng multiplicatively weighted
VD. Trong đó mỗi trường học được gán trọng số theo quy mô của trường [37].


™ Lập kế hoạch di chuyển cho robot (motion planning)
Mục đích của bài tốn là di chuyển một robot dạng đĩa tròn từ điểm bắt đầu s tới điểm kết
thúc t vượt qua chướng ngại vật là các đoạn thẳng, giả sử từng cặp đoạn thẳng này không
cắt nhau [1].

11


Hình 4.3: Di chuyển robot từ s tới t qua các vật cản sử dụng giản đồ Voronoi [1].

Khi Robot di chuyển qua kẽ hở nằm giữa hai đoạn thẳng l1 và l2 với mọi điểm x khoảng
cách
d(x,li) = min {d(x,y), y∈ li}
đến chướng ngại vật phải lớn nhất. Điều này sẽ đạt được nếu robot di chuyển theo
bisector của l1 và l2. Hay robot sẽ di chuyển theo các cạnh Voronoi với các site là tập hợp
các đoạn thẳng chướng ngại vật.
Nếu thay robot bằng một convex polygon và chướng ngại vật là các polygon. Robot sẽ di
chuyển theo giản đồ Voronoi dựa trên convex distance (xem 5.1.1).

12


Chương 5: Multiplicatively Weighted Convex
Distance FunctionVoronoi Diagram
trong mặt phẳng
Trong nhiều năm, các nghiên cứu về giản đồ Voronoi trên mặt phẳng không chỉ tập trung
trên khoảng cách Euclid với các point site mà còn được mở rộng trên nhiều dạng khoảng
cách khác nhau như giản đồ Voronoi với trọng số (weighted Voronoi diagram),
Karlsruhe metric (hay còn được gọi là Moscow metric), hàm khoảng cách lồi (convex

distance function),... Tổng quan về các mở rộng của giản đồ Voronoi có thể tham khảo
tại [1] và [35].
Một mở rộng quan trọng của giản đồ Voronoi với các dạng khoảng cách khác nhau là
giản đồ Voronoi dựa trên hàm khoảng cách là hàm khoảng cách lồi với các point site.
Convex distance function là sự mở rộng tổng quát của khoảng cách Euclid giữa hai site
trong mặt phẳng. Giản đồ Voronoi được xây dựng dựa trên convex distance function
được ứng dụng giải quyết nhiều vấn đề như lập kế hoạch di chuyển cho robot qua các
chướng ngại vật (motion planning), các bài toán xác định vị trí (location problem),...
Giản đồ Voronoi trong mặt phẳng dựa trên convex distance được giới thiệu bởi Lee
[26] cho họ Lp-metric (với 1 ≤ p ≤ ∞). Icking et al. [20, 21] và Ma [32] khảo sát các tính
chất của bisector giữa hai site dựa trên hàm convex distance trong mặt phẳng và không
gian 3 chiều. Ma [32] giới thiệu các tính chất của giản đồ Voronoi dựa trên convex
distance trong mặt phẳng và không gian 3 chiều.
Trong phần này ta sẽ trình bày hướng nghiên cứu mở rộng giản đồ Voronoi theo hướng
mới multiplicatively weighted convex distance function Voronoi diagram (MWCD) tức là
giản đồ Voronoi dựa trên convex distance function trong đó mỗi site được gán một trọng
số riêng cho nó trên mặt phẳng. Giản đồ Voronoi dựa trên convex distance function với
trọng số trong mặt phẳng có những nét tương đồng nhất định với multiplicatively
weighted Voronoi diagram trong mặt phẳng dựa trên khoảng cách Euclid được giới thiệu
bởi Aurenhammer and Edelsbrunner [3]. Trong các mục dưới đây ta sẽ giới thiệu về
convex distance, một số tính chất và định nghĩa quan trọng, tiến hành khảo sát các tính
chất của bisector giữa hai site cũng như các tính chất của giản đồ Voronoi dựa trên
convex distance có trọng số. Ta cũng chú trọng tới việc giải quyết các trường hợp suy
biến thay vì né tránh nó bằng các giả định theo kiếu ba điểm không thẳng hàng hay
không xảy ra suy biến,...

13


5.1 Một số tính chất của Convex distance

Trong mặt phẳng tọa độ R2, cho C là một tập đóng (compact), lồi (convex) chứa gốc
(origin) O, được gọi là tâm (center) của C, bên trong nó. Cho hai điểm p và q trong mặt
phẳng. Ta dịch chuyển C bằng một vector p và xét tia pq , tia này cắt biên của C, ký
hiệu là ∂C , tại một điểm q’.
Định nghĩa 5.1.1 [32] Một convex distance function từ p tới q theo C được định nghĩa
như sau:
d ( p, q )
d C ( p, q ) =
d ( p, q ')
Trong đó: d(p, q) là khoảng cách Euclid giữa hai điểm p và q.

q
p

C

q’

O

Hình 5.1.1: Convex distance giữa hai điểm p và q với tập C cho trước.

Dễ thấy dC(p, q) là hệ số mà C (với tâm p) phải mở rộng để biên của nó chứa q. C được
gọi là đường tròn đơn vị (unit circle) hay tập các điểm q thỏa dC (0, q ) ≤ 1 .
Ta gọi C + p là C sau khi dịch chuyển bỏi vector p và kC là C sau khi được mở rộng với
tỉ số k.
Convex distance function dC được gọi là strictly convex nếu biên của C là strictly convex
(biên của C không chứa bất kỳ đoạn thẳng nào) và gọi là smooth nếu C là smooth (tại mỗi
điểm trên biên của C có duy nhất một tiếp tuyến với C). Nếu C đối xứng qua tâm O khi
đó dC sẽ được gọi là một convex distance đối xứng (symmetric convex distance function).

Tính chất 5.1.1 Tính chất metric của dC(p, q).
1) dC ( p, q ) ≥ 0 và dC ( p, q ) = 0 iff p = q .
2) dC ( p, q) = dC (q, p) nếu và chỉ nếu C đối xứng qua tâm O.
3) dC ( p, q) ≤ dC ( p, r ) + dC (r , q) (bất đẳng thức tam giác).
Vậy trong 3 tính chất cơ bản của metric dC(p, q) chỉ thỏa tính chất 1) 3). Riêng với
tính chất thứ 2) chỉ thỏa mãn khi C đối xứng qua tâm O, điều này có nghĩa là khoảng
cách từ p tới q và khoảng cách từ q tới p không phải lúc nào cũng như nhau.

14