Chương 1 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN Trong chương này, luận văn trình bày lại một số kiến thức cơ bản trong lý thuyết đồ thị, các khái niệm về đa giác đơn, cây đối ngẫu, hình ống tay và “Phễu” trong không gian hai chiều được trình bày và là nền tảng để xây dựng thuật toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn có sử dụng kĩ thuật “Phễu”.1 ĐA GIÁC ĐƠN Để giải quyết được bài toán về tìm đường đi ngắn nhất giữa hai điểm s và t nằm trong đa giác đơn mà đường đi ngắn nhất đó không cắt biên của đa giác, chúng tôi sẽ trình bày lại một vài định nghĩa sau: Hình 1.1 Một đường gấp khúc đơn. [7] Một đường gấp khúc đơn là một dãy các điểm qi (i = 1, 2,. , k ), ở đó tất cả các cặp điểm liền kề như qi và qi+1 được nối thành một đoạn (i = 1, 2,. , k − 1) và không có hai đoạn không liên tiếp nào cắt nhau (xem hình 1.
Khi chuỗi đường gấp khúc đơn là một vòng tròn khép kín sẽ xác định được một đa giác. [7] Một đa giác đơn có n đỉnh P = (q1 , q2 ,. , qn ) là một chuỗi đa giác với qn+1 = q1 , tức là qn được nối với q1. Một đường chéo của P là một đoạn [qi , qj ], j 6= i + 1 và không cắt bất kì một cạnh nào của P.
P được tam giác phân nếu miền trong của nó được chia ra bởi n − 2 tam giác và n − 3 đường chéo.3 Đa giác đơn P được tam giác phân bởi các đường chéo [q1 , q3 ], [q3 , q6 ], [q6 , q4 ]. Chúng ta thấy trên hình 1.3 là một đa giác đơn 6 đỉnh đã được tam giác phân thành 4 tam giác bởi 3 đường chéo.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU Các khái niệm sau đây sẽ là kiến thức cơ sở cho bài toán về tìm đường đi ngắn nhất trong một đa giác đơn hoặc một khối đa diện. Ở đây, luận văn chỉ trình bày các khái niệm liên quan đến đồ thị vô hướng.4 Minh hoạ một đồ thị vô hướng. [15] Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), trong đó V là một tập khác rỗng gồm các đỉnh, E là một tập gồm các cạnh - mỗi cạnh có hai đầu mút tạo bởi hai đỉnh của đồ thị vô hướng G.
Khi biểu diễn một đồ thị vô hướng trên mặt phẳng ta biểu diễn các đỉnh của đồ thị bởi các đường tròn nhỏ, các cạnh còn lại được biểu diễn bằng một đường cong nối các đỉnh của cạnh. Ta kí hiệu một cạnh e được giới hạn bởi hai đầu mút là hai đỉnh a và b là e = [a, b], khi đó a và b được gọi là hai đỉnh kề nhau, hai cạnh có chung một đỉnh được gọi là hai cạnh kề nhau. Cung dạng [b, b] với b ∈ V được gọi là khuyên (xem Hình 1. Bậc của v là số các đỉnh kề với v.
Khi đó G là một đồ thị vô hướng được biểu diễn như Hình 1. [15] Với G = (V, E) là một đồ thị vô hướng, một hành trình được định nghĩa trong G là một dãy v0 e1 v1 e2. en vn sao cho với mọi i = 0, 1, 2,. , n, ei là cạnh kề của các đỉnh vi−1 và vi.
Khi đó, n được gọi là độ dài, v0 được gọi là đỉnh đầu, vn được gọi là đỉnh cuối. Ta nói rằng, một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Một hành trình được gọi là đường nếu các đỉnh của hành trình đó đều khác nhau. Một hành trình khép kín được gọi là chu trình nếu nó có độ dài ít nhất là 3 và khi xoá đi một đỉnh cuối thì trở thành đường.
[15] Một đồ thị G = (V, E) được gọi là liên thông nếu hai đỉnh vi và vj khác nhau bất kì của G tồn tại một hành trình vô hướng trong G với đỉnh đầu là vi và đỉnh cuối là vj. [15] Một đồ thị vô hướng liên thông không có khuyên, không có chu trình được gọi là cây.5 Minh hoạ một cây. Coi một đa giác đơn P đã được tam giác phân giống như một không gian đồ thị G mà ở đó mỗi mặt của tam giác sẽ tương ứng với một nút điểm của đồ thị và mỗi cạnh sẽ được tạo thành bởi việc nối hai nút điểm với nhau. Khi đó, đồ thị đối ngẫu sẽ trở thành một cây mà các đỉnh của nó có bậc lớn nhất là 3.
[7] Cây đối ngẫu của một đa giác đơn P đã được tam giác phân là một đồ thị G = (V, E) sao cho mỗi nút của V tương ứng với một tam giác thuộc đa giác đơn P và mỗi cạnh của E nối hai nút thuộc V của hai tam giác có chung một đường chéo trong P. Xét một đa giác đơn P = (q1 , q2 ,. , q11 ) được tam giác phân bởi các đường chéo [q2 , q3 ], [q2 , q4 ], [q4 , q5 ],[q5 , q6 ], [q6 , q7 ], [q7 , q8 ], [q8 , q9 ], [q6 , q8 ]. Xác định một cây đối ngẫu của đa giác đơn P .6 Đa giác đơn được P được tam giác phân bởi các đường chéo.7 Cây đối ngẫu là đường màu đỏ của đa giác đơn P.
Kí hiệu 4(s) là tam giác chứa điểm s và 4(t) là tam giác chứa điểm t, đường đi ngắn nhất từ điểm s tới t trong đa giác đơn P là π. Hơn nữa, mỗi cạnh thuộc π lần lượt cắt mỗi đường chéo của P (theo thứ tự từ s đến t) tại một điểm duy nhất, và mỗi đường chéo của P chia P thành hai miền tương ứng chứa s và t. Vì thế đường đi ngắn nhất từ s tới t nằm trong P cũng sẽ cắt mỗi đường chéo 11 của P tại một điểm duy nhất. Hay nói một cách khác, đường đi ngắn nhất giữa hai điểm s và t cũng sẽ là một đường gấp khúc và bổ đề sau đây sẽ làm rõ hơn về điều này.
[7] Xét một đa giác đơn P có n đỉnh đã được tam giác phân bởi các đường chéo, ta kí hiệu là di (trong đó i = 1,. Cho S là tập hợp tất cả các điểm đầu mút của các đường chéo di (i = 1,. , n − 3) và đường đi ngắn nhất, khi đó tất cả các đỉnh của đường đi ngắn nhất giữa s và t sẽ nằm trong tập S ∪ {s, t}. Do S là tập hợp các điểm đầu và điểm cuối của các đường chéo nên ở đây S chính là tập hợp tất cả các đỉnh của đa giác đơn P.
Vậy để tìm đường đi ngắn nhất giữa hai điểm s và t chúng ta sẽ cần phải tìm đường đi ngắn nhất từ s tới tất cả các điểm đầu mút của các đường chéo của P và điểm cuối cùng là điểm t. Hợp tất cả các đường đi ngắn nhất này sẽ tạo thành một cây G với gốc là điểm s.3 HÌNH ỐNG TAY VÀ HÌNH “PHỄU” Để tìm các đỉnh của cây G = (V, E) không cần phải đi xét hết tất cả các đỉnh của đa giác đơn P mà chỉ cần tìm ra một miền thuộc đa giác đơn P cũng chứa đường đi ngắn nhất giữa hai điểm s và t. Để xác định được hình ống tay hay miền đa giác P cần xác định được miền chứa đường ngắn nhất từ s tới t. [7] Một đa giác đơn P đã được tam giác phân được gọi là hình ống tay nếu cây đối ngẫu của đa giác đơn P đó là một đường gấp khúc đơn.
Chuyển bài toán tìm đường đi ngắn nhất giữa hai điểm của một đa giác đơn thành bài toán tìm đường đi ngắn nhất giữa hai điểm của một hình ống tay, việc tìm hình ống tay giúp giảm bớt việc xét các đỉnh thuộc đa giác đơn P mà đường ngắn nhất từ s tới t không đi qua, nhưng để giải quyết bài toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn thì Lee và Preparata đã đưa ra khái niệm về “phễu”. Xét một hình ống tay 12 Hình 1.8 Hình ống tay P 0 là miền được tô màu nâu. P có n đỉnh, s là điểm thuộc hình ống tay P , di là các đường chéo của P (1 ≤ n ≤ n − 3). Chúng ta sẽ kí hiệu: vi (1) và vi (2) là hai điểm đầu mút của đường chéo di (với 1 ≤ i ≤ n−3).
SP (s, vi (j) ) là đường đi ngắn nhất từ s tới điểm cuối vi (j) với (j = 1, 2) nằm trong đa giác đơn P .1 thì tập tất cả các đỉnh mà đường SP (s, vi (j) ) đi qua với (j = 1, 2) đều là các đỉnh thuộc đa giác đơn P. Gọi v là điểm chung của SP (s, vi (1) ) và SP (s, vi (2) ) sao cho v là đỉnh xa nhất tính từ s.9 Hình ảnh minh hoạ cho hình phễu Ri với chóp phễu là v và cạnh chung di. [7] Một miền Ri được giới hạn bởi SP (v, vi (1) ), SP (v, vi (2) ) và đường chéo di với (1 ≤ i ≤ n − 3) sẽ được gọi là “phễu”, v được gọi là chóp của phễu. Giả sử các đường gấp khúc con đề cập sau khác rỗng, khi đó SP (v, vi (j) ) với j = 1, 2 sẽ là một đường gấp khúc lồi hướng vào trong.
Khi đó, chúng ta có mệnh đề sau. [7] Nếu SP (v, vi (j) ) là các đường gấp khúc lồi hướng vào trong thì cũng có nghĩa là mặt lồi của nó hướng vào miền trong của P. Bằng phương pháp quy nạp, chúng ta sẽ chỉ ra được phễu Ri nằm hoàn toàn trong đa giác đơn P. Xét các đường chéo ds , ds+1 ,.
, di−1 bị cắt bởi các đường gấp khúc (1) (2) SP (v, vi (1) ) và SP (v, vi (2) ). Rõ ràng, 4vvs vs = Rs nằm hoàn toàn trong đa giác đơn P. Giả sử rằng Ri−1 ⊂ P , khi đó miền Ri mới được tạo thành từ miền Ri−1 hợp thêm với một phần hoặc toàn bộ một tam giác (tam giác chứa cạnh di ) nằm trong đa giác đơn P. Từ đó, chúng ta cũng suy ra được Ri ⊂ P .