Tài liệuBiểu đồ Vonoroi

BIỂU ĐỒ VORONOI Giả sử bạn ở trong Ban cố vấn về kế hoạch của một hệ thống các siêu thị và hiện đang có các kế hoạch nhằm mở các chi nhánh mới tại một số site xác định. Để dự đoán xem liệu một chi nhánh mới có khả năng mang lại lợi nhuận hay không, bạn phải ước tính số khách hàng mà nó sẽ thu hút được. Để làm được điều này, bạn phải xác định được hành vi của các khách hàng tiềm năng: họ quyết định địa điểm để mua sắm như thế nào? Một câu hỏi tương tự nảy sinh khi phân theo địa lý xã hội, khi nghiên cứu hành vi kinh tế trong một nước: khu vực nào là khu vực thương mại của một thành phố? Trên lý thuyết, chúng ta có một tập hợp các địa điểm trung tâm – còn được gọi là các site- cung cấp các hàng hoá và dịch vụ chính và chúng ta muốn biết với các site/site này thì những người sống ở đó ai là người chấp nhận mua hàng hoá và dịch vụ tại chỗ. Để trả lời câu hỏi này, chúng ta giả định đơn giản như sau: + Giá của hàng hoá hoặc dịch vụ bằng nhau ở mọi nơi + Chi phí cho hàng hoá và dịch vụ bằng giá cộng chi phí vận chuyển + Chi phí vận chuyển tới một site bằng số khoảng cách ơclit đến nơi đó nhân với giá cố định của mỗi đơn vị khoảng cách. + Người mua cố gắng tối thiểu hoá chi phí cho hàng hoá và dịch vụ yêu cầu Thông thường, những giả định này không hoàn toàn được thoả mãn: hàng hoá ở site này có thể sẽ rẻ hơn ở site khác và ngay cả trong một thành phố, chi phí vận chuyển từ nơi này đến nơi khác có thể không tương đương nhau theo khoảng cách Ơclit giữa các điểm. Nhưng mô hình trên có thể đưa ra các khu vực thương mại của các site một cách tương đối. Những khu vực nơi mà các hành vi của người dân ở đó khác với dự đoán của mô hình này có thể phải được nghiên cứu sâu hơn, để tìm ra nguyên nhân dẫn đến hành vi khác lạ này. Điều chúng ta quan tâm nằm trên đường biểu diễn hình học của mô hình trên. Những giả định của mô hình giúp ta chia nhỏ một vùng lớn thành các vùng nhỏ- khu vực thương mại- mà những người dân sống tại cùng một khu vực luôn đến cùng một chỗ. Giả định này ngụ ý rằng, mọi người đơn giản mua hàng hoá tại nơi gần nhất- tình trạng công bằng thực tế. Điều này có ý nghĩa rằng khu vực thương mại của một nơi nhất định bao gồm tất cả các điểm gần hơn các site khác. Hình 7.1 đưa ra một ví dụ. Các site ở trong hình vẽ này là trung tâm của 12 tỉnh ở Hà Lan. Mô hình mà mọi điểm được phân chia bởi các nơi gần nhất được gọi là mô hình phân chia Voronoi của tập các site. Từ biểu đồ Voronoi, chúng ta có thể lấy được tất cả các thông tin về khu vực thương mại của site và các site liên quan. Ví dụ, nếu một vùng gồm 2 site có đường ranh giới sau đó 2 site này có thể cạnh tranh trực tiếp với nhau về những khách hàng- những người sống ở khu vực gần đường ranh giới. Biểu đồ Voronoi là một cấu trúc hình học đa tác dụng. Chúng ta đã miêu tả một ứng dụng của nó đối với địa lý xã hội. Ngoài ra biểu đồ Voronoi còn có các ứng dụng trong vật lý, thiên văn học, rô-bốt và rất nhiều các lĩnh vực khác. Nó cũng liên quan chặt chẽ tới một cấu trúc hình học quan trọng khác: cái được gọi là tam giác Delaunay mà chúng ta sẽ nghiên cứu trong chương 9. Trong chương này, chúng ta sẽ giới hạn ở những đặc tính cơ bán và xây dựng biểu đồ Voronoi của tập hợp các điểm trên mặt phẳng. 7.1 Định nghĩa và các tính chất cơ bản Gọi khoảng cách Ơclit giữa hai điểm p và q là dist (p,q) Trong một mặt phẳng chúng ta có: P= (p1,p2,….,pn) là tập hợp của n khoảng cách điểm trong một mặt phẳng. Các điểm là các site. Chúng ta định nghĩa biểu đồ Voronoi của P giống như việc chia mặt phẳng thành nhiều ô, mỗi ô tương ứng với một site của P, với tính chất là một điểm q nằm trong ô tương ứng với một site pi khi và chỉ khi dist(q,pi)<dist(q,pj) với pjP và j¹i. Chúng ta ký hiệu biểu đồ Voronoi của P là Vor(P); ô tương ứng với site pi là V(pi). Chúng ta gọi đó là ô Voronoi của pi. Theo thuật ngữ như đã giới thiệu về chương này: V(pi) được gọi là khu vực thương mại của site pi. Bây giờ chúng ta sẽ tìm hiểu sâu hơn về biểu đồ Voronoi. Trước tiên, chúng ta nghiên cứu cấu trúc ô Voronoi đơn. Với 2 điểm p &q trong mặt phẳng, chúng ta xác định được bờ của p và q là đường trung trực của đoạn thẳng pq. Bờ này chia mặt phẳng thành 2 nửa mặt phẳng. Chúng ta gọi nửa mặt phẳng chứa p là h(p,q) và nửa mặt phẳng chứa q là h(q,p). Nhớ rằng rh(p,q) Ûdist(r,p)dist(r,q). Từ đó, ta nhận được các nhận xét sau: Nhận xét 7.1 (thiếu công thức) Do vậy n(pi) là phần cắt nhau của n-1 nửa mặt phẳng, do đó là một vùng đa giác lồi được bao (có thể không kín) bởi tối đa n-1 đỉnh và tối đa n-1 cạnh. Biểu đồ Voronoi hoàn chỉnh sẽ như thế nào? Chúng ta đã nhìn thấy mỗi ô của biểu đồ là phần giao của một số nửa mặt phẳng do đó biểu đồ Voronoi là một phần nhỏ của mặt phẳng mà các cạnh là các đoạn thẳng và một vài cạnh là các nửa đường thẳng. Trừ khi tất cả các site nằm trên cùng một đường thẳng thì sẽ không có cạnh nào là đường thẳng đầy đủ. Định lý 7.2 Cho P là tập của n điểm trên mặt phẳng. Nếu tất cả các site nằm trên cùng một đường thẳng thì Vor(p) bao gồm n-1 đường song song và n ô. Nếu không Vor(p) được kết nối và các cạnh của nó là đoạn hoặc nửa đường thẳng. Chứng minh: Phần đầu của định lý ta dễ dàng chứng minh được. Do vậy, giả định không phải tất cả các site trong P là thẳng hàng. Trước hết, chúng ta đi chứng minh rằng các cạnh của Vor(p) là đoạn hoặc nửa đường thẳng. Chúng ta đã biết rằng các cạnh của Vor(p) là các phần đường thẳng, có nghĩa là các phần của các bờ giữa các cặp site. Bây giờ, giả sử điều cần chứng minh là sai, tức là có cạnh e của Vor(p) là một đường thẳng đầy đủ. Khi đó, e nằm trên đường bao của các ô Voronoi n(pi), n(pj). pk thuộc p là điểm không thẳng hàng với pi, pj. Bờ của pj, pk không song song với e, do vậy nó cắt e. Nhưng khi đó, một phần của e nằm trong h(pk,pj) và không thể nằm trên đường bao của n(pi) bởi vì nó gần pk hơn pj. Mâu thuẫn. Tiếp theo ta sẽ chứng minh rằng Vor(P) sẽ được kết nối. Nếu như Vor(P) chưa được kết nối thì sẽ tồn tại một ô Voronoi n(pi) chia mặt phẳng làm 2 phần. Do ô Voronoi là lồi, n(pi) sẽ bao gồm 1 dải được bao bởi 2 đường thẳng song song. Nhưng chúng ta đã chứng minh được rằng các cạnh của biểu đồ Voronoi không thể là một đường thẳng. Mâu thuẫn. Vậy định lý được chứng minh. Bây giờ, chúng ta đã hiểu cấu trúc của biểu đồ Voronoi, chúng ta sẽ nghiên cứu tính phức tạp của nó, đó là tổng số đỉnh và cạnh của nó. Vì có n site và mỗi ô Voronoi có tối đa n-1 đỉnh và cạnh, độ phức tạp của Vor(p) tối đa là dạng bậc 2. Tuy nhiên, Vor(p) thực tế chưa chắc đã có độ phức tạp bậc 2: ta dễ dàng xây dựng một ví dụ mà một ô Voronoi có độ phức tạp bậc nhất, nhưng liệu tất cả các ô Voronoi đều có độ phức tạp bậc nhất hay không? Định lý sau sẽ chỉ ra rằng điều đó không đúng và số trung bình của đỉnh của một ô Voronoi là nhỏ hơn 6. Định lý 7.3 Một biểu đồ Voronoi của tập n site trong mặt phẳng có số đỉnh tối đa là (2n-3) và số cạnh tối đa là 3n-6. Chứng minh: Nếu như n site này cùng nằm trên một đường thẳng thì định lý được suy ra từ định lý 7.2. Xét trường hợp còn lại: Chúng ta sẽ chứng minh định lý này bằng việc sử dụng công thức Ơle. Định lý Ơle phát biểu rằng đối với mọi đồ thị kín có: mv: số nút, mc: số cung, mf: số mặt Thì: mv - mc + mf = 2 Chúng ta không thể áp dụng công thức Ơle trực tiếp cho Vor(P) do Vor(P) có một số cạnh là một nửa đường thẳng nên không thỏa mãn điều kiện của công thức Ơle. Để giải quyết tình trạng này, ta thêm một đỉnh Vm tại vô cực vào tập các đỉnh và nối tẩt cả các cạnh có một đầu không giới hạn của Vor(p) vào đỉnh này. Bây giờ, chúng ta có một biểu đồ đã được nối thỏa mãn điều kiện của công thức Ơle. Chúng ta nhận được mối quan hệ sau giữa nv, số đỉnh của Vor(p), ne: số cạnh của Vor(p) và n số site: (nv+1) + n - ne = 2 ( 7.1) Hơn nữa, tất cả các cạnh trong biểu đồ được mở rộng có chính xác 2 đỉnh do vậy, nếu chúng ta cộng tất cả các đỉnh chúng ta sẽ có 2 lần số cạnh. Bởi vì, tất cả các đỉnh (bao gồm cả Vm) có bậc tối thiểu là 3, nên ta có 2 ne3 (nv+1) ( 7.2) Cùng với công thức 7.1 định lý được chứng minh. Chúng ta kết thúc phần này bằng việc xem xét một đặc điểm về các cạnh và các đỉnh của biểu đồ Voronoi. Chúng ta biết rằng các cạnh là một phần của các bờ của các cặp site và các đỉnh là điểm cắt giữa các bờ này. Có một số bậc hai bờ trong khi đó độ phức tạp của Vor(p) chỉ là bậc nhất. Do vậy, không phải tất cả các bờ là cạnh của Vor(p) và không phải tất cả các điểm cắt là đỉnh của biểu đồ Voronoi. Để xác định bờ hoặc điểm cắt nào là hình thành lên Vor(P) chúng ta xây dựng định nghĩa như sau: Với một điểm q, chúng ta định nghĩa vòng tròn rỗng lớn nhất của q đối với p – kí hiệu là Cp(q) là vòng tròn lớn nhất với q là tâm và không chứa bất cứ site nào của P bên trong nó. Định lý sau sẽ cho biết đặc điểm của các đỉnh và cạnh của biểu đồ Voronoi. Định lý 7.4 Với biểu đồ Voronoi Vor(p) của một tập n điểm thuộc p - Một điểm q là đỉnh của Vor(p) óvòng tròn rỗng lớn nhất của Cp(q) chứa tối thiểu 3 site trên nó. - Bờ giữa hai site pi và pj tạo nên một cạnh của Vor(P) ócó một điểm q thuộc E2 mà Cp(q) chứa cả pi và pj trên nó nhưng không thêm một site nào nữa. Chứng minh: - Giả sử có một điểm q mà Cp(q) chứa 3 site hoặc nhiều hơn trên đường biên của nó. Cho pi, pj và pk là 3 trong số các site đó. Vì bên trong Cp(q) là rỗng; nên q phải nằm trên đường biên của n(pi), n(pj), n(pk) và q phải là một đỉnh của Vor(p). Mặt khác, mọi đỉnh q của Vor(p) có tối thiểu 3 cạnh do vậy, với tối thiểu ô Vonoroi V(pi), V(pj);V(pk). Đỉnh q phải cách đều pi, pj và pk và không được có một site nào khác gần q hơn nữa. Do vậy, bên trong vòng tròn đi qua pi, pj và pk không chứa thêm một site nào nữa. - Giả sử có một điểm q với tính chất đã được nêu ra trong định lý. Vì Cp(q)=dist(q,pj)dist(q,pk) cho tất cả. Theo đó, q nằm trên một cạnh hoặc đỉnh của Vor(p. Phần đầu của định lý ngụ ý rằng, q không thể là một đỉnh của Vor(p). Do vậy, q nằm trên một cạnh của Vor(p) chính là bờ của pi và pj. - Ngược lại, bờ pi và pj là một cạnh của Vor(p). Vòng tròn rỗng lớn nhất của bất kỳ điểm q nào thuộc cạnh này phải chứa pj và pi trên đường biên của nó và không chứa thêm site nào nữa. 7.2. Tính toán biểu đồ Voronoi Trong phần trước chúng ta đã nghiên cứu biểu đồ Voronoi. Bây giờ, chúng ta tính toán nó. Nhận xét 7.1 đề cập một cách đơn giản để làm điều này với mỗi site của Pi, tính phần giao thông thường của các nửa mặt phẳng h(pi, pj) với j¹i, dùng cơ sở toán học đã đưa ra trong chương IV. Theo cách này, chúng ta có độ phức tạp O(n logn) với mỗi ô Voronoi, dẫn đến O(n2 logn) cho toàn biểu đồ Voronoi, với giả thiết rằng chúng ta có thể gộp các ô Voronoi để hình thành biểu đồ. Liệu chúng ta có thể làm tốt hơn được không? Sau khi tính toán, ta có tổng độ phức tạp của biểu đồ Voronoi là bậc nhất. Như vậy câu trả lời là có: Thuật toán đường trượt trên nửa mặt phẳng mô tả dưới đây thường được biết như thuật toán Fortune theo tên của người phát minh- tính biểu đồ Voronoi theo độ phức tạp O(n logn). Bạn có thể tìm kiếm một thuật toán nhanh hơn, ví dụ có độ phức tạp bậc nhất. Tuy nhiên, bất kỳ thuật toán nào để tính biểu đồ Voronoi phải có độ phức tạp tối thiểu W(nlogn). Do vậy, thuật toán Forture là tối ưu. Chiến lược trong thuật toán đường trượt trên mặt phẳng là trượt đường thẳng nằm ngang- đường trượt từ đỉnh đến đáy mặt phẳng. Trong khi trượt, thông tin được duy trì liên quan đến cấu trúc muốn tính toán. Chính xác hơn, thông tin được duy trì về sự giao cắt của cấu trúc với các đường trượt. Trong khi đường trượt di chuyển xuống thì thông tin không thay đổi, ngoại trừ các điểm đặc biệt xác định- điểm sự kiện. Cố gắng áp dụng phương pháp chung này để tính toán cho biểu đồ Voronoi với tập P= (p1, p2,…,pn) điểm site trên mặt phẳng. Theo mô hình đường trượt trên mặt phẳng, chúng ta di chuyển đường trượt nằm ngang l tính từ đỉnh xuống đáy mặt phẳng. Mô hình quan tâm duy trì điểm cắt của biểu đồ Voronoi với đường trượt. Không may là điều này không dễ dàng. Bởi vì, phần Vor(p) ở trên l phụ thuộc không chỉ vào các site nằm trên l mà còn phụ thuộc vào cả các site nằm dưới l. Nói cách khác, khi đường trượt đạt đến đỉnh cao nhất của ô Voronoi V(pi) nó không chỉ chạm phải site tương ứng của pi. Do vậy, chúng ta có tất cả các thông tin cần thiết để tính đỉnh. Chúng ta buộc phải áp dụng mô hình đường trượt trên mặt phẳng theo một cách khác đơn giản hơn: thay vì duy trì/lưu trữ giao điểm của biểu đồ Voronoi của các đường trượt, chúng ta lưu trữ thông tin về phần biểu đồ Voronoi chứa các site nằm trên l vì các site này không bị thay đổi bởi các site nằm dưới l. Biểu diễn nửa mặt phẳng trên của l là l+. Phần của biểu đồ Voronoi nằm trên l không bị thay đổi Nói cách khác, với mỗi điểm q Îl+, chúng ta biết chắc rằng site nào là gần nhất với nó. Khoảng cách của một điểm q Îl+ tới bất kỳ site nào nằm dưới l luôn luôn lớn hơn khoảng cách từ q®l. Do vậy. site gần nhất của q không thể nằm dưới l nếu q tối thiểu là gần so với site nào đó Îl+ bằng q®l. Quỹ tích của điểm gần qi Îl+ hơn l là một đường Parabol. Do vậy, quỹ tích của các điểm gần với bất kỳ site nào trên l hơn là khoảng cách từ nó tới l là các đường cong Parabol. Chúng ta gọi trật tự của các đường cong Parabol là đường bờ biển- BL. Một cách khác để quan sát BL như sau: Mọi site pi nằm trên đường trượt định nghĩa một parabol hiệu chỉnh bi. BL có tính chất: tại mỗi hoành độ, nó đi qua điểm thấp nhất của một trong số các parabol. Nhận xét 7.5 BL là một x- đơn điệu nghĩa là tất cả các trục dọc chỉ cắt nó duy nhất tại một điểm. Dễ dàng nhận ra rằng một đường parabol có thể tham gia nhiều hơn một lần vào BL. Chúng ta sẽ xét sau là bao nhiêu đoạn có thể tham gia. Nhớ rằng, điểm gấp khúc giữa các cung parabol khác nhau tạo nên BL nằm trên cạnh của biểu đồ Voronoi. Đây không phải là một sự trùng hợp: điểm gấp khúc đánh dấu chính xác biểu đồ Voronoi trong khi đường trượt di chuyển từ đỉnh xuống đáy. Những tính chất này của BL có thể được chứng minh bằng hình học. Do vậy, thay vì lưu trữ chúng ta di chuyển đường trượt l của chúng ta. Chúng ta không lưu trữ BL một cách chi tiết, liên tục từ lúc l bắt đầu di chuyển. Bây giờ, tạm quên đi biểu diễn BL như thế nào cho đến khi chúng ta hiển thị thay dổi kết hợp cấu trúc của nó như thế nào và ở đâu. Điều này xảy ra khi một cung parabol thêm vào và khi cung parabol nằm trong một điểm và biến mất ở đâu trên BL. Hiện tượng này xảy ra khi đường trượt l gặp một site mới. Khi dó đường parabol được định nghĩa bởi site này có độ rộng bằng 0. Một đoạn trục dọc được nối từ BL tới site nào đó. Khi đường trượt tiếp tục di chuyển xuống thì parabol mới nằm dưới BL cũ bây giờ là một phần của BL. Hình 7.2 minh họa cho quá trình này. Chúng ta gọi hiện tượng mà tại dó một site mới được bổ sung là một site hiện tượng. Vấn đề gì xảy ra với biểu đồ Voronoi tại site hiện tượng? Xem lại điểm gấp khúc trên BL đánh dấu cạnh của biểu đồ Voronoi. Tại một site hiện tượng, 2 điểm gấp khúc mới xuất hiện- bắt đầu đánh dấu các cạnh. Thực tế, ban đầu các điểm gấp khúc mới xuất hiện, sau đó di chuyển theo các hướng ngược nhau để dánh dấu cùng một cạnh. Đầu tiên, cạnh này không được nối với biểu đồ Voronoi trên đường trượt. Tiếp sau đó, chúng ta sẽ nhìn thấy ngay sau đó chính xác khi nào điều này sẽ xảy ra- cạnh tăng và sẽ đi lên cạnh khác và nó sẽ được kết nối với biểu đồ. Do vậy, bây giờ chúng ta hiểu cái gì đã xảy ra tại site hiện tượng: một cung mới xuất hiện trên BL và một cạnh mới của biểu đồ Voronoi bắt đầu được đánh dấu. Liệu một cung mới có thể xuất hiện trên BL theo một cách khác? Câu trả lời là không. Bổ đề 7.6 Cách duy nhất để một cung mới xuất hiện trên BL là thông qua một site hiện tượng. Chứng minh: Giả sử ngược lại rằng đã tồn tại một parabol bj được định nghĩa bởi một vị tri pj thông qua BL. Theo đó, có 2 trường hợp có thể xảy ra. Trường hợp 1 bj xuất hiện ở giữa của một cung của Parabol bj. Bây giờ vấn đề sẽ xảy ra như sau: bi; bj là các đường tiếp tuyến , chúng co chính xác một điểm giao nhau. Gọi ly là tung độ của đường trượt hiện tại và điểm tiếp xúc. Nếu pi=(pix.piy) khi đó: Công thức tính bi tương tự. Sử dụng pix và piy lớn hơn ly. Dễ dàng cho thấy bi và bj không thể cắt nhau chỉ tại một điểm. Do vậy, parabol bi và bk, q là giao điểm của bi và bk và tại đó bj xuất hiện trên BL. Giả định rằng bi nằm bên trái q, bk nằm bên phải q như trên hình 7.3. Khi đó, có một vòng tròn C đi qua pivà pj và px, các site tạo nên parabol. Vòng tròn này cũng tiếp xúc với đường trượt l tại điểm pj. Trật tự theo chiều kim đồng hồ trên C là p(pi, pj, pk) bởi vì bj được giả định xuất hiện ở giữa các cung của bi và bk. Di chuyển đường trượt xuống một đoạn cực nhỏ trong khi vẫn giữ vòng tròn tiếp xúc với l xem hình 7.3. Khi đó, trong C sẽ không còn rỗng và C vẫn đi qua pj. Hệ quả của Bổ đề này là BL bao gồm tối đa (2n-1) đường cong parabol. Mỗi khi có một site tham gia, làm tăng thêm một đường con mới và chia tối đa một đường con hiện tại làm hai và không có cách nào khác để một đường cong xuất hiện trên BL. Trường hợp 2 của hiện tượng trong thuật toán đường trượt trên mặt phẳng là một đường cong của BL hội tụ tại một điểm và biến mất. Gọi a’ là cung sẽ bị biến mất, a và a’’ là hai cung liền trước và liền sau của a’ trước khi nó biến mất. Cung a và a’’ không thể là 2 nhánh của cùng một parabol, khả năng này có thể loại bỏ giống như cách đã chứng minh ở khả năng đầu tiên của Bổ đề 7.6. Do vậy, 3 đường cung a,a’ và a’’ được xác định bởi 3 site khác nhau pi, pj, pk. Bây giờ, a’ biến mất, các parabol được xác định bởi 3 site này đồng thời đi qua điểm q. Điểm q cách đều từ l tới mỗi site và có một vòng tròn đi qua pi, pj, pk với q là tâm và tiếp xúc với l. Không thể có một site nào nằm trong vòng tròn này: nếu site nào đó gần q hơn, khoảng cáhc từ q®l, mâu thuẫn với thực tế rằng qÎBL. Tiếp theo q là một đỉnh của biểu đồ Voronoi. Điều này không mấy ngạc nhiên như chúng ta đã biết điểm gấp khúc trên BL đánh dấu biểu đồ Voronoi. Do vậy, khi một cung biến mất khỏi BL và 2 điểm gấp khúc gặp nhau, 2 cạnh của biểu đồ Voronoi cũng gặp nhau. Chúng ta gọi hiện tượng mà tại dó, đường trượt tiếp xúc với dường tròn thông qua 3 site, tạo nên đường cong liên tục trên Bl là vòng tròn hiện tượng. Từ đó, chúng ta có thể kết luận Bổ đề như sau: Bổ đề 7.7 Cách duy nhất mà qua đó một cung hiện tại có thể biến mất khỏi BL là thông qua một vòng tròn hiện tượng. Bây giờ chúng ta biết cấu trúc kết hợp của BL thay đổi như thế nào tại một site hiện tượng một đường cong mới xuất hiện và tại một vòng tròn hiện tượng một cung hiện tại bị loại mất. Chúng ta cũng biết điều này liên quan như thế nào đến biểu đồ Voronoi thông qua cách xây dựng: tại một site hiện tượng một cạnh mới bắt đầu xuất hiện và tại một vòng tròn hiện tượng có 2 cạnh mới để tạo nên một đỉnh. Nó còn tìm ra cấu trúc dl phù hợp để lưu trữ các thông tin cần thiết trong suốt quá trình trượt. Mục tiêu của chúng ta là tính toán biểu đồ Voronoi vì vậy chúng ta cần một cấu trúc dl để lưu trữ phần biểu đồ Voronoi đã được tính toán. Chúng ta cũng cần 2 cấu trúc dữ liệu chuẩn cho bất kỳ một thuật toán đường trượt: một hàng sự kiện và một cấu trúc biểu diễn tình trạng của đường trượt. Cấu trúc thứ 2 là để biểu diễn BL. Những cấu trúc dữ liệu này được tiến hành theo cách sau: - Chúng ta lưu trữ biểu đồ Voronoi dưới dạng xây dựng cấu trúc dữ liệu thông thường cho các phần, danh sách cạnh được nối 2 đầu. Tuy nhiên, một biểu đồ Voronoi không hoàn toàn là sự chia nhỏ như định nghĩa trong chương II. Nó có những cạnh là nửa hay toàn bộ đường thẳng và những cạnh này không được biểu diễn trong danh sách cạnh được nối 2 đầu. Trong suốt quá trình xây dựng đây không phải là một vấn đề, bởi vì việc biểu diễn các BL, mô tả sau sẽ làm được điều này để thâm nhập vào các phần tương ứng dánh sách cnạh được nối 2 đầu một cách đầy đủ trong suốt quá trình xây dựng. Nhưng sau khi tính toán, chúng ta muốn có danh sách cạnh được nối 2 đầu có giá trị. Cuối cùng chúng ta thêm một đường bao có dạng hộp, nó đủ to để chứa tất cả các đỉnh của biểu đồ Voronoi. Sau đó, phần cuối cùng chúng ta tính sẽ là phần hộp và phần biểu đồ Voronoi nằm trong hộp này. - BL được biểu diễn bởi cây nhị phân cân