Kiến thức về tập lồi
Giả sử x, y ∈ E 2 , λ ∈ [0; 1] Đoạn thẳng[x;y]là tập hợp {λx+ (1−λ)y}.
- Nếu x 6= y, phần trong của [x, y] là tập hợp
- Nếu x 6= y, phần trong của [x, y] và chứa điểm x là tập hợp
- Nếu x 6= y, phần trong của [x, y] và chứa điểm y là tập hợp
1.1.1 Định nghĩa (Xem [8]) Giả sử S ⊂ E 2 , tập S được gọi là lồi nếu với mọi x ∈ S, y ∈ S thì [x, y] ⊂ S.
1.1.2 Định nghĩa (Xem [9])x ∈ E 2 , x được gọi làtổ hợp lồi củax 1 , , x m nếu tồn tại λ i ≥ 0 (i = 1, , m), P m i=1 λ i = 1 sao cho x= Pm i=1λ i x i
1.1.3 Mệnh đề (Xem [9]) Giả sử S ⊂ E 2 là tổ hợp lồi; x 1 , x 2 , , x m ∈
Chứng minh Ta chứng minh mệnh đề bằng phương pháp quy nạp.
Theo định nghĩa 1.1.1 ta luôn có λ 1 x 1 + λ 2 x 2 ∈ S.
Giả sử mệnh đề là đúng với m = k,∀k ≥ 2 ta cần chứng minh mệnh đề đúng với m = k + 1, nghĩa là: ∀x 1 , x 2 , , x k+1 ∈ S,∀λ i ≥ 0 (i = 1, k + 1),
Không mất tính tổng quát ta giả sử 0 ≤ λ k+1 < 1 (vì nếu λ k+1 = 1) thì λ 1 = λ 2 = = λ k = 0 suy ra ta cóx ∈ S) Khi đó 1−λ k+1 = λ 1 +λ 2 + + λ k > 0 và λ i
1−λ k+1 = 1 nên theo giả thiết quy nạp ta cóP k i=1 λ i
Với các điểm y ∈ S và x k+1 ∈ S, ta có 1−λ k+1 ,(1−λ k+1 ) +λ k+1 = 1, do đó x = (1−λ k+1 )y +λ k+1 x k+1 ∈ S.
1.1.4 Mệnh đề (Xem [8]) Giả sử A ⊂ E 2 Khi đó A là tập lồi khi và chỉ khi (α+β)A = αA+ βA với mọi α ≥ 0, β ≥ 0.
1.1.5 Mệnh đề (Xem [9]) Nếu A là tập lồi thì bao đóng clA của A cũng là tập lồi.
Chứng minh Lấyx 0 , x 1 ∈ clA Đặtx := λx 0 + (1−λ)x 1 với 0 ≤ λ ≤ 1 Giả sử U là lân cận lồi của điểm 0 Dox 0 , x 1 ∈ clA nên (x i +U)∩A 6= φ, (i = 0,
1) Suy ra tồn tại x / i ∈ (x i +U)∩A, (i = 0, 1) Đặt x / := λx / 0 + (1−λ)x / 1 , dễ thấy x / ∈ Ado x / 0 , x / 1 ∈ A Khi đó x / ∈ λ(x 0 +U) + (1−λ)(x 1 +U) =x+U.
Do đó (x+U)∩A 6= φ, suy ra x∈ clA.
Vậy clA là tập lồi.
(a) Tổ hợp tuyến tính (hữu hạn) của các tập lồi là các tập lồi.
(b) Ảnh và nghịch ảnh của một tập lồi qua ánh xạ tuyến tính là tập lồi.
1.1.7 Mệnh đề (Xem [8]) Giao của một họ tùy ý các tập lồi là tập lồi.
Chứng minh Giả sử A i (i ∈ i) là các tập lồi Đặt A = T i∈IA i Lấyx 1 , x 2 ∈
A, hiển nhiên x 1 , x 2 ∈ A i , ∀i ∈ I Mặt khác do A i lồi, với ∀i ∈ I nên ta có: λx 1 + (1−λ)x 2 ∈ A i ,∀λ ∈ [0,1],∀i ∈ I.
1.1.8 Định nghĩa (Xem [9]) Giao tất cả các tập lồi chứa A gọi là bao lồi của A Ký hiệu: convA.
(a) convA là tập lồi nhỏ nhất chứa A.
(b) A là tập lồi khi và chỉ khi A = convA.
1.1.10 Mệnh đề (Xem [9]) convA là tập hợp tất cả các tổ hợp lồi của A.
1.1.11 Mệnh đề (Xem [3]) Bao lồi của họ hữu hạn điểm trong E 2 là hình đa giác lồi có các đỉnh thuộc họ điểm đã cho.
1.1.12 Định nghĩa (Xem [3]) Ta gọi x ∈ M là điểm cực biên của tập lồi
Biểu đồ Voronoi
Cho P = {p 1 , p 2 , , p n } là tập hợp n điểm phân biệt trong mặt phẳng Euclidean, được gọi là các vị trí Biểu đồ Voronoi là một phân hoạch phẳng của P thành n miền, trong đó mỗi miền tương ứng với một điểm trong P Cụ thể, nếu điểm q thuộc miền ứng với p i, thì khoảng cách từ q đến p i sẽ nhỏ hơn hoặc bằng khoảng cách từ q đến bất kỳ điểm nào khác p j trong P, với i khác j Ký hiệu cho biểu đồ này là Vor(P).
• Miền Voronoi ứng với p i , ký hiệu V or(p i ).
Trong bài viết này, chúng ta sẽ xem xét hai điểm p1 và p2 trong không gian E2 Đường trung trực B(p1, p2) được ký hiệu là B12, là tập hợp các điểm x có khoảng cách đến p1 bằng khoảng cách đến p2 Điều này có thể được minh họa qua Hình 1.1.
Vì vậy, biểu đồ Voronoi là cả 2 miền đều không bị chặn Hai miền này là hai nửa mặt phẳng có bờ là đường thẳng B 12
Hình 1.1: Hình biểu diễn hai vị trí p 1 và p 2
1.2.3 Ví dụ Cho 3 điểm p 1 , p 2 , p 3 trong E 2 Ta có tam giác p 1 p 2 p 3 chứa các đường trung trực B 12 , B 23 và B 31 (như hình vẽ) Do vậy giao điểm của
Hình 1.2: Ba vị trí: p 1 , p 2 và p 3
Ba đường trung trực B12, B23 và B31 là tâm của đường tròn ngoại tiếp tam giác P1, P2, P3 Do đó, biểu đồ Voronoi được hình thành từ ba miền không bị chặn, được tạo ra bởi các giao điểm OB23 ∩ OB31, OB23 ∩ OB12 và OB12 ∩ OB31.
1.2.4 Tính chất (Xem [6]) Mọi miền Voronoi V(p i ) là tập lồi.
Do V(p i ) là phần giao nhau của (n - 1) nửa mặt phẳng nên nó có thể không bị chặn, là miền đa giác lồi, mở giới hạn bởi (n - 1) đỉnh và (n - 1) cạnh.
1.2.6 Ví dụ Trong mặt phẳng cho P = {p 1 , p 2 , p 3 } với p 1 (0; 0), p 2 (4; 0), p 3 (4; 4) Tìm Vor(p i ).
Gọi B ij là đường trung trực của đoạn thẳng p i p j , ∀i 6= j , i, j = 1,2,3.
Ta viết được các phuơng trình đường trung trực B ij là:
Gọi (h ij ) , ∀i 6= j, với i, j = 1,2,3 là nửa mặt phẳng chứa p i với biên là đường trung trực B ij Khi đó: V(p i ) = T i6=j h ij Vậy ta có:
Định lý 1.2.7 nêu rằng, cho tập hợp các vị trí P = {p1, p2, , pn} trên mặt phẳng, nếu tất cả các vị trí này nằm trên một đường thẳng, thì Vor(P) sẽ tạo thành (n - 1) đường thẳng song song Ngược lại, nếu các vị trí không nằm trên cùng một đường thẳng, thì Vor(pi) (với i = 1, 2, , n) sẽ có tính liên thông, với các cạnh là đoạn thẳng hoặc nửa đường thẳng.
1.2.8 Định lý (Xem [4]) Cho tập P = {p 1 , p 2 , , p n } là tập gồm n điểm trong mặt phẳng Với n ≥ 3, thì biểu đồ Voronoi Vor(P) có nhiều nhất2n−5 đỉnh và 3n−6 cạnh.
Cho P = {p 1 , p 2 , , p n } là một tập hợp các điểm trong không gian E 2 Đối với một điểm v, ta xác định các đường tròn rỗng có tâm tại v, ký hiệu là C(v) Tập hợp C(v) bao gồm các đường tròn có tâm v đi qua các điểm trong P, với điều kiện rằng phần bên trong của các đường tròn này không chứa bất kỳ điểm nào trong P.
Biểu đồ Voronoi V or(P) có các tính chất quan trọng: Đỉnh v của Vor(P) tồn tại khi và chỉ khi đường tròn C(v) đi qua hơn 2 điểm trong tập P Hơn nữa, đường trung trực của đoạn nối hai điểm p i và p j sẽ xác định một cạnh của Vor(P) nếu tồn tại một điểm v nằm trên đường trung trực đó, sao cho đường tròn C(v) đi qua cả p i và p j.
Giả sử có một điểm v mà C(v) chứa ba vị trí p i, p j và p k Nếu C(v) rỗng, v phải nằm trên đường biên của V(p i), V(p j), V(p k), dẫn đến việc v là một đỉnh của Vor(P) Mọi đỉnh v của Vor(P) có tối thiểu ba cạnh, do đó có ít nhất ba ô Voronoi V(p i), V(p j) và V(p k) Điểm v cách đều p i, p j, p k và không có vị trí nào gần v hơn, nghĩa là bên trong đường tròn đi qua p i, p j, và p k không có thêm vị trí nào, tức là C(v) rỗng Nếu v có tính chất như trong định lý, với d(v, p j) ≤ d(v, p k), v nằm trên một cạnh hoặc đỉnh của Vor(P) Phần đầu của định lý cho thấy v không thể là đỉnh của Vor(P), vì vậy v nằm trên một cạnh của Vor(P), chính là bờ của p i, p j, mà cạnh này là đường trung trực của p i, p j.
Đường trung trực p_i và p_j là một cạnh của Vor(P), với đường tròn rỗng tâm v nằm trên cạnh này, chứa hai điểm p_j và p_i trên biên của nó mà không có điểm nào khác.
1.2.10 Bài toán Cho p j = (p j,x , p j,y ) cố định và đường thẳng l cố định có phương trình y = l y Tìm tập hợp của tất cả những điểm m ∈ E 2 thỏa mãn: d(m, p j ) = d(m, l).
Bài giải: a) Phần thuận: Giả sử p j = (p j,x , p j,y ) cố định và đường thẳng l cố định có phương trình y = l y Gọi (x, y) là tọa độ của điểm m trong E 2 , Ta có: d(m, p j ) = (x−p j,x ) 2 + (y −p j,y ) 2 (1.2.1) d(m, l) = (y−l y ) 2 (1.2.2)
⇔2(p j,y −l y )y = x 2 −2p j,x x+p 2 j,x +p 2 j,y −l y 2 (1.2.3) + Nếu l y 6= p j,y khi đó từ (1.2.3), ta có: y = 1
2(p j,y −l y )(x 2 −2p j,x x+p 2 j,x + p 2 j,y −l y 2 ) (1.2.4) Phương trình (1.2.4) là phương trình của đường cong Parabol.
+ Nếu l y = p j,y thì từ (1.2.3), ta có: x 2 −2p j,x x+p 2 j.x = 0
Phương trình (1.2.5) là phương trình của đường thẳng Đường thẳng này song song với trục tung đi qua điểm (p j,x ; 0) b) Phần đảo:
Giả sử p j = (p j,x , p j,y ) cho trước và một điểm m bất kỳ thuộc parabol có phương trình (1.2.4) nói trên Khi đó, ta có: m(x; 1
Mặt khác, với p j và mọi điểm m nói trên thỏa mãn phương trình (1.2.5) hay ta có x = p j,x ⇒ l y = p j,y
Do đó, ta có: d(m, p j ) = d(m, l). c) Kết luận: Vậy tập hợp các điểm mà thỏa mãn điều kiện của bài toán là đường cong parabol có phương trình: y = 1
Với điểm p i (x i; y i) cho trước, tập hợp các điểm m ∈ E 2 thỏa mãn điều kiện d(m; p i) ≤ d(m; l), trong đó l là đường thẳng có phương trình y = l y (với y khác y i), tạo thành miền chứa điểm p i, được giới hạn bởi đường cong parabol có phương trình y = 1.
1.2.12 Bổ đề (xem [4]) Một cung mới xuất hiện khi đường quét qua vị trí có sự kiện.
Chứng minh Giả sử, ngược lại rằng tồn tại một Parabol β j xác định được bởi vị trí p j Có 2 khả năng xẩy ra:
Trong một parabol β i xác định bởi vị trí p i, khả năng 1 cho thấy β j xuất hiện ở giữa một cung của β i, nơi mà hai đường này tiếp xúc nhau tại một điểm duy nhất Tại điểm tiếp xúc này, l y được xác định là tung độ của đường trượt hiện tại.
Với p j = (p jx , p jy ) khi đó: β j : y = 1
2(p j,y −l y )(x 2 −2p j,x x+p 2 j,x +p 2 j,y −l y 2 ) và với p i = (p ix , p iy ), ta có: β i : y = 1
Nếu p j,y < l y và p i,y < l y thì ta dễ dàng chứng minh được β i và β j không chỉ cắt nhau chỉ tại 1 điểm Do đó, parabol β j không bao giờ vượt qua giữa cung parabol β i
Parabol β j có thể xuất hiện giữa hai cung β i và β k, trong đó β i và β k là các phần của parabol Điểm giao nhau của β i và β k được gọi là q, với β i nằm bên trái và β k nằm bên phải của điểm q.
Có một đường tròn C đi qua ba điểm pi, pj và pk, xác định các parabol tương ứng Đường tròn C tiếp xúc với đường thẳng l Các vị trí pi, pj, pk trên đường tròn C được sắp xếp theo chiều kim đồng hồ từ pi đến pj, pk, và quay trở lại pi.
Khi đường thẳng l di chuyển từ trên xuống dưới, đường tròn C vẫn tiếp xúc với l, nhưng giờ đây là một đường tròn khác rỗng và vẫn đi qua điểm p j Trong quá trình này, một trong hai vị trí p i hoặc p k sẽ lọt vào bên trong đường tròn Do đó, trong một lân cận đủ nhỏ của điểm q, parabol β j không thể xuất hiện khi đường thẳng l di chuyển, vì khoảng cách từ p i hoặc p k đến đường l sẽ gần hơn so với khoảng cách từ p j đến đường l.
Tập P = {p1, p2, , pn} gồm n điểm trong mặt phẳng có thể tạo ra tối đa (2n - 1) đường cong parabol Mỗi khi thêm một điểm mới, số lượng đường cong tăng lên và có khả năng chia một đường cong hiện tại thành hai đường mới.
1.2.14 Bổ đề (Xem [4]) Sự kiện điểm (a i ) ∈ P
(1) Đường quét l quét qua điểm a i Áp dụng sự tìm kiếm của đường l để xác định các cung ở phía dưới các vị trí a i Cho a j là vị trí tương ứng.
(2) Vận dụng quá trình chèn và phân chia cung phía dưới vị trí a i , chèn một vị trí mới trong danh sách Q Do vậy thay thế < , a j , > bởi < , a j , a i , a j , >.
(3) Tạo một cạnh mới của biểu đồ Voronoi Cạnh này nằm trên đường trung trực của a i a j , phân chia 2 miền Voronoi V(a i ) và V(a j ).
Kiểm tra bộ ba cung liên tiếp a j a i , a i , a i a j, chúng ta xác định các cung bên trái a i, cung a i và cung bên phải a i Để đảm bảo tính hội tụ, cần xem xét các điểm gãy ở cung bên trái nhằm chèn sự kiện đường tròn, và thực hiện tương tự đối với cung bên phải.
Cho 3 điểm a i , a j và a k là các điểm sinh ra sự kiện này.
(1) Vận dụng quá trình xóa cung a j ở trên từ đường bờ biển Do vậy, loại ra cung này.
Tam giác phân Delaunay
Phép tam giác phân Delaunay, ký hiệu D(P), là một phương pháp phân chia tập hợp điểm P = {p1, p2, , pn} trong không gian hai chiều E2, sao cho đường tròn đi qua ba đỉnh của bất kỳ tam giác nào không chứa điểm nào khác trong tập hợp.
1.3.2 Tính chất (Xem [6]) Phần trong của mỗi mặt tam giác phân De- launay không chứa vị trí p i (i = 1,2, , n) nào.
1.3.3 Tính chất (Xem [4], [6]) Nếu P có k đỉnh nằm trên bao lồi thì D(P) có (2n−2−k) tam giác và (3n−3−k) cạnh.
Chứng minh Gọi n, n v , n e lần lượt là số đỉnh, số tam giác và số cạnh của D(P).Theo giả thiếtP có k đỉnh nằm trên bao lồi nên D(P) cók cạnh biên.
Mỗi cạnh biên của đa giác P tương ứng với một cạnh của một tam giác duy nhất, trong khi mỗi cạnh không phải biên là cạnh chung của hai tam giác Do đó, số cạnh của D(P) được tính theo công thức: n e = 3n v − k.
2(3n v + k) (1.3.1) Mặt khác, theo hệ thức Euler ta có : n−n e + (n v + 1) = 2 (1.3.2)
Từ ( 1.3.1 ) và ( 1.3.2 ) ta có điều phải chứng minh.
1.3.4 Tính chất (Xem [6]) D(P) là duy nhất nếu không có 4 điểm của
P nằm trên một đường tròn.
1.3.5 Mối liên hệ giữa biểu đồ Voronoi và tam giác phân De- launay (Xem [6])
1 Mỗi mặt (Tam giác) của D(P) tương ứng với một đỉnh của V(P).
2 Mỗi cạnh của D(P) tương ứng với một cạnh của V(P).
3 Tâm v của đường tròn C(v) đi qua 3 điểm p 1 , p 2 , p 3 tương ứng với tâm đường tròn trong tam giác phân Delaunay.
4 Trong 1.2.2 thì (p i p j ) là cạnh của D(P) Ngược lại, Với mỗi cạnh De- launay thì có một đường tròn rỗng.
Tam giác phân Delaunay được thể hiện qua các đường nét đứt, chồng lên biểu đồ Voronoi phía dưới, được minh họa bằng các đường nét liền.
THUẬT TOÁN TÌM BIỂU ĐỒ VORONOI
Bài toán
Bài toán : Trong E 2 cho tập P = {p 1 , p 2 , , p n } gồm n điểm Tìm biểu đồ Voronoi của tập P.
Minh họa ý tưởng
Ý tưởng giải quyết bài toán này là sử dụng một đường trượt l với phương nằm ngang có phương trình y = l y, cho phép trượt từ trên xuống dưới qua các vị trí p i, trong đó i = 1, 2, 3,
Sắp xếp các vị trí p i theo tung độ từ cao đến thấp, với các vị trí lần lượt là a 1 , a 2 , a 3 , Trượt thanh l từ trên xuống dưới để vẽ các parabol có đường chuẩn là đường thẳng l, với tiêu điểm là các vị trí a 1 , a 2 , a 3 , Các cặp parabol sẽ giao nhau tại các giao điểm, và những giao điểm này chính là các đỉnh của biểu đồ Voronoi Các đỉnh này nằm trên các cạnh của biểu đồ Voronoi, từ đó giúp xác định biểu đồ Voronoi cần tìm dựa vào định nghĩa và các tính chất trong chương I.
Thuật toán
Input: Một tập P = {p 1 , p 2 , , p n } gồm n điểm trong mặt phẳng.
Step 1: Sắp xếp danh sách các điểm p i (i= 1, 2, , n) theo thứ tự có tung độ giảm dần Các vị trí sau khi được sắp xếp là Q= {a 1 , a 2 , , a n }, (j = 1, 2, ,n).
• Lấy sự kiện điểm a có tung độ lớn nhất ra khỏi Q.
• Nếu a := p i ∈ P thì xử lý sự kiện điểm p i
• Ngược lại xử lý sự kiện đường tròn.
Step 3: Cập nhật đỉnh và cạnh của Voronoi một cách thích hợp để được biểu đồ Voronoi. end
2.3.2 Ví dụ Trong mặt phẳng Oxy cho tập P = {p 1 , p 2 , p 3 , p 4 , p 5 } gồm 5 điểm p 1 (2; 0), p 2 (−1;−2), p 3 (1; 2), p 4 (0; 3), p 5 (−2;−3) Tìm Vor(P).
Bước 1: Sắp xếp các vị trí p 1 , p 2 , p 3 , p 4 , p 5 theo thứ tự có tung độ giảm dần lần lượt là: a 1 = p 4 , a 2 = p 3 , a 3 = p 1 , a 4 = p 2 , a 5 = p 5
• Khi l y = 3 , ta chỉ có cung β 1 là đường thẳng x = 3, parabol β 1 có độ rộng bằng 0.
Tại vị trí a 2 : Khi l y = 2, ta có β 2 là một đường thẳng, parabol β 2 có độ rộng bằng 0.
• Khi 0
