Sơ đồ Voronoi là cách chia một mặt phẳng thành các ô, mỗi ô gắn với một điểm cho trước, sao cho mọi chỗ trong ô ở gần điểm của ô đó hơn bất kỳ điểm nào khác. Nếu các điểm là những cây ATM, mỗi ô Voronoi là vùng mà ai đứng trong đó thì cây ATM gần nhất chính là cây của ô. Đường ranh giữa hai ô luôn nằm trên đường trung trực của đoạn nối hai điểm, nên có thể vẽ bằng thước và compa.
Định nghĩa trong một câu và ba tính chất
Cho một tập điểm gọi là điểm hạt nhân (site) P₁, P₂, …, Pₙ. Ô Voronoi của Pᵢ là tập mọi điểm X trên mặt phẳng sao cho khoảng cách từ X tới Pᵢ không lớn hơn khoảng cách từ X tới bất kỳ Pⱼ nào khác. Từ định nghĩa đó suy ra:
- Cạnh ô nằm trên đường trung trực. Những điểm cách đều P₁ và P₂ là đường trung trực của đoạn P₁P₂. Ranh giữa hai ô kề nhau là một đoạn của đường này.
- Mỗi ô là một đa giác lồi. Ô của Pᵢ là giao của các nửa mặt phẳng "gần Pᵢ hơn Pⱼ", mà giao của các tập lồi thì lồi. Không có ô hình lưỡi liềm hay hình chữ U.
- Đỉnh ô cách đều ba điểm. Chỗ ba ô gặp nhau là tâm đường tròn đi qua ba điểm hạt nhân tương ứng, và bên trong đường tròn đó không có điểm hạt nhân nào khác.
Vẽ tay một sơ đồ ba điểm: ví dụ ba trường học
Một khu dân cư có ba trường tiểu học, đặt trên lưới toạ độ theo km: trường A ở (0, 0), trường B ở (4, 0), trường C ở (0, 4). Mỗi gia đình muốn biết trường nào gần nhà mình nhất theo đường chim bay.
- Trung trực AB. Trung điểm AB là (2, 0), AB nằm ngang, nên trung trực là đường thẳng đứng x = 2. Bên trái gần A, bên phải gần B.
- Trung trực AC. Trung điểm (0, 2), AC thẳng đứng, nên trung trực là đường nằm ngang y = 2.
- Trung trực BC. Trung điểm (2, 2), BC có hướng (−4, 4), nên trung trực vuông góc với nó, đi qua (2, 2) theo hướng (1, 1): đường y = x.
- Điểm gặp nhau. Ba đường đồng quy tại (2, 2). Khoảng cách từ đó tới mỗi trường là √(2² + 2²) = √8 ≈ 2,83 km.
Kết quả: ô của A là góc phần tư phía dưới trái của điểm (2, 2), tức x ≤ 2 và y ≤ 2. Ô của B là phần bên phải x = 2 và dưới đường y = x. Ô của C là phần phía trên y = 2 và trên đường y = x. Nhà ở toạ độ (3, 1) thuộc ô B, cách B √2 ≈ 1,41 km, cách A √10 ≈ 3,16 km, cách C √18 ≈ 4,24 km. Đúng như sơ đồ.
Điểm (2, 2) còn đáng chú ý theo một nghĩa khác: xét trong tam giác ABC, đó là chỗ mà quãng đường tới trường gần nhất dài nhất, 2,83 km. Muốn mở trường thứ tư để rút ngắn quãng đường đi học xa nhất, nơi đầu tiên nên xem xét là quanh đỉnh Voronoi này.
Từ Descartes tới Voronoy: một ý tưởng được đặt tên nhiều lần
| Năm | Người | Đóng góp |
|---|---|---|
| 1644 | René Descartes | Trong Principia philosophiae có hình vẽ các vùng ảnh hưởng của những "xoáy" quanh các ngôi sao, gần giống một sơ đồ Voronoi, dù ông không định nghĩa toán học. |
| 1850 | Peter Gustav Lejeune Dirichlet | Dùng cách chia này khi nghiên cứu dạng toàn phương trong hai và ba chiều; vì thế còn gọi là phép lát Dirichlet. |
| 1854 | John Snow | Trong nghiên cứu dịch tả ở London, vẽ đường bao vùng mà từ đó đi bộ tới máy bơm phố Broad gần hơn các máy bơm khác. |
| 1908 | Georgy Voronoy | Nhà toán học người Ukraina thuộc Đế quốc Nga, định nghĩa tổng quát cho không gian n chiều. Tên ông được gắn vào khái niệm. |
| 1911 | Alfred Thiessen | Nhà khí tượng Mỹ dùng để tính lượng mưa trung bình vùng; giới thuỷ văn gọi là đa giác Thiessen. |
| 1934 | Boris Delaunay | Học trò của Voronoy, định nghĩa phép tam giác hoá đối ngẫu, nay gọi là tam giác Delaunay. |
| 1986 | Steven Fortune | Công bố thuật toán quét đường dựng sơ đồ Voronoi cho n điểm trong thời gian tỉ lệ n log n. |
Một ý tưởng xuất hiện độc lập trong thiên văn, lý thuyết số, dịch tễ học và khí tượng là dấu hiệu nó chạm vào một điều rất cơ bản: câu hỏi "cái nào gần tôi nhất".
Đa giác Thiessen: tính lượng mưa trung bình bằng sơ đồ Voronoi
Đây là ứng dụng kinh điển, vẫn được dạy trong giáo trình thuỷ văn. Một lưu vực có ba trạm đo mưa. Trận mưa vừa qua, trạm 1 đo 80 mm, trạm 2 đo 120 mm, trạm 3 đo 50 mm. Lượng mưa trung bình lưu vực là bao nhiêu?
Lấy trung bình cộng (80 + 120 + 50) / 3 ≈ 83 mm là sai nếu các trạm phân bố không đều. Thiessen đề xuất: vẽ sơ đồ Voronoi của ba trạm, cắt theo ranh lưu vực, rồi lấy trung bình có trọng số theo diện tích từng ô. Giả sử ô của trạm 1 rộng 30 km², trạm 2 rộng 15 km², trạm 3 rộng 55 km²:
- Trạm 1: 80 × 30 = 2.400
- Trạm 2: 120 × 15 = 1.800
- Trạm 3: 50 × 55 = 2.750
- Tổng: 6.950, chia cho 100 km² ra 69,5 mm.
Chênh gần 14 mm so với trung bình cộng, vì trạm mưa nhiều đại diện cho vùng nhỏ còn trạm mưa ít đại diện cho vùng rộng. Phương pháp giả định mưa đều trong từng ô, nên ở vùng núi mưa thay đổi theo độ cao, người ta dùng thêm các cách nội suy khác.
Đếm cạnh và đỉnh: vì sao trung bình mỗi ô gần sáu cạnh
Với n điểm hạt nhân (n ≥ 3, không thẳng hàng hết), công thức Euler cho đồ thị phẳng V − E + F = 2 giới hạn được kích thước sơ đồ: số đỉnh Voronoi không quá 2n − 5, số cạnh không quá 3n − 6. Mỗi cạnh là biên chung của đúng hai ô, nên tổng số cạnh tính theo từng ô không quá 2(3n − 6) = 6n − 12. Chia cho n ô, trung bình mỗi ô có ít hơn 6 cạnh, và khi n lớn thì tiến sát 6.
Nghĩa là: dù rải điểm ngẫu nhiên đến đâu, "ô trung bình" vẫn là một lục giác. Khi các điểm xếp thành lưới tam giác đều, mọi ô đều là lục giác đều, đúng hình tổ ong. Đây cũng là lý do bản đồ vùng phủ sóng trong sách giáo khoa viễn thông luôn được vẽ bằng lục giác.
Về tốc độ: thuật toán ngây thơ xét mọi cặp điểm tốn thời gian cỡ n² hoặc hơn; với một triệu điểm là quá chậm. Thuật toán Fortune quét một đường thẳng ngang qua mặt phẳng, duy trì một "bờ biển" gồm các cung parabol, và chỉ tốn cỡ n log n phép tính. Hầu hết thư viện hình học ngày nay dựng sơ đồ Voronoi qua tam giác Delaunay rồi lấy đối ngẫu.
Khi khoảng cách không phải đường chim bay
Định nghĩa Voronoi chỉ cần một cách đo khoảng cách. Đổi cách đo là đổi hình ô:
- Khoảng cách Manhattan (đi theo ô bàn cờ, chỉ ngang và dọc): ranh giới gồm các đoạn thẳng đứng, nằm ngang và chéo 45°, như trong một khu phố lưới ô cờ.
- Khoảng cách theo đường đi thật: một con sông không có cầu làm nhà ở bờ bên kia, dù gần trường theo đường chim bay, lại thuộc ô của một trường khác. Ở đồng bằng sông Cửu Long, nơi kênh rạch chia cắt, sơ đồ theo đường đi thật khác xa sơ đồ thước kẻ.
- Có trọng số: nếu một điểm "mạnh" hơn (trạm phát sóng công suất lớn, siêu thị to), ranh giới bị đẩy về phía điểm yếu và có thể cong thành cung tròn.
- Trên mặt cầu: dùng khoảng cách theo vòng tròn lớn, các cạnh ô là cung của vòng tròn lớn.
Sơ đồ Voronoi trong tự nhiên
Nhiều hoa văn tự nhiên trông giống sơ đồ Voronoi vì cùng một cơ chế: nhiều tâm cùng lớn ra với tốc độ như nhau, gặp nhau ở chỗ cách đều.
- Bọt xà phòng xếp lớp mỏng trên mặt phẳng.
- Các mảng lông trên da hươu cao cổ, đường gân trên cánh chuồn chuồn.
- Các tế bào thực vật xếp sát nhau, các tinh thể kim loại lớn lên từ nhiều mầm khi nguội.
- Lãnh thổ của các con cá đực đào tổ trên đáy ao: mỗi con giữ một vùng quanh tổ, các vùng ép vào nhau thành những ô gần lục giác.
Cần nói rõ: đây là những hình gần giống Voronoi. Vết nứt bùn khô chẳng hạn hình thành theo cơ chế co ngót khác, các góc thường gần 90° hoặc 120° tuỳ giai đoạn, không phải lúc nào cũng khớp định nghĩa.
Góc nhìn hôm nay: tự vẽ một sơ đồ Voronoi
- Bằng giấy bút. Đánh dấu năm cây xăng hay năm hiệu thuốc quanh nhà trên một bản đồ in, nối các cặp gần nhau, kẻ đường trung trực bằng compa, giữ phần nằm giữa. Kết quả cho biết nhà mình thuộc "vùng" nào, và chỗ nào xa mọi cửa hàng nhất.
- Bằng phần mềm. Các phần mềm bản đồ GIS miễn phí như QGIS có sẵn công cụ dựng đa giác Voronoi từ một lớp điểm.
- Đọc thêm. Giáo trình hình học tính toán (computational geometry) có chương riêng về Voronoi và Delaunay; giáo trình thuỷ văn có phần đa giác Thiessen.
Câu hỏi thường gặp
Sơ đồ Voronoi là gì?
Sơ đồ Voronoi chia mặt phẳng thành các ô quanh những điểm cho trước, mỗi ô gồm mọi chỗ gần điểm của nó hơn mọi điểm khác. Ranh giữa hai ô nằm trên đường trung trực của đoạn nối hai điểm.
Cách vẽ sơ đồ Voronoi bằng tay thế nào?
Nối các cặp điểm gần nhau, kẻ đường trung trực của từng đoạn nối, rồi giữ lại phần đường trung trực nằm giữa hai điểm gần nhất. Chỗ ba đường gặp nhau là tâm đường tròn qua ba điểm, cũng là một đỉnh của sơ đồ.
Đa giác Thiessen là gì?
Đa giác Thiessen là tên giới thuỷ văn, khí tượng gọi sơ đồ Voronoi dựng từ các trạm đo. Alfred Thiessen dùng nó năm 1911 để tính lượng mưa trung bình vùng, lấy trọng số theo diện tích ô của từng trạm.
Sơ đồ Voronoi khác tam giác Delaunay thế nào?
Hai cấu trúc là đối ngẫu của nhau. Nối hai điểm hạt nhân khi ô Voronoi của chúng có chung cạnh, ta được tam giác Delaunay. Voronoi chia vùng, Delaunay nối các điểm láng giềng.
Sơ đồ Voronoi dùng để làm gì?
Dùng để tìm cơ sở gần nhất (trường, bệnh viện, trạm phát sóng), tính lượng mưa trung bình vùng, chọn chỗ đặt cửa hàng mới, mô phỏng tinh thể và tế bào, và dựng lưới tính toán trong kỹ thuật.