Một số tính chất của tập lồi trắc địa và bao lồi trắc địa

2.2. Một số tính chất của tập lồi trắc địa và bao lồi trắc địa . . . . . . 14 2.3. Thuật toán tìm điểm chung của họ hữu hạn các tập lồi trắc địa trong một đa giác đơn . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Thuật toán tìm bao lồi trắc địa 24 3.1. Đa giác đơn yếu . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2. Thuật toán tìm bao lồi trắc địa của một đa giác trong một đa giác đơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3. Thuật toán tìm bao lồi trắc địa của một tập hợp hữu hạn điểm trong một đa giác đơn . . . . . . . . . . . . . . . . . . . . . . . . . 27 Kết luận 32 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2LỜI NÓI ĐẦU Tập lồi và bao lồi là những khái niệm cơ bản của Giải tích lồi. Bài toán tìm bao lồi của một tập hợp hữu hạn điểm trong mặt phẳng, một đường gấp khúc hoặc một đa giác là bài toán quan trọng của Hình học tính toán. Đã có một số nhà toán học nghiên cứu về tập lồi mở rộng, như H. X. Phú (1999) đưa ra tập γ-lồi (xem [15]), P. T. An và N. N. Hải (2004) đưa ra tập δ-lồi (xem [5])... Năm 1989, khái niệm tập lồi trắc địa (trong mặt phẳng) được xuất hiện lần đầu tiên trong bài báo của Toussaint (xem [23]). Tập lồi trắc địa là một mở rộng của tập lồi, hơn nữa nó còn có nhiều ứng dụng trong thực tế: trong công nghiệp (xem [23]), trong chế tạo Rôbốt (xem [9])... Trong khóa luận này, chúng tôi nghiên cứu một số tính chất của tập lồi trắc địa và bao lồi trắc địa. Đồng thời, chúng tôi đưa ra thuật toán tìm điểm chung của một họ hữu hạn các tập lồi trắc địa trong một đa giác đơn và trình bày chi tiết thuật toán tìm bao lồi trắc địa của Toussaint. Do đó, chúng tôi lựa chọn đề tài Một số tính chất của tập lồi trắc địa và bao lồi trắc địa. Khóa luận này được chia làm 3 chương. Chương 1. Kiến thức cơ sở Trong chương này, chúng tôi trình bày khái quát một số kiến thức là cơ sở cho nội dung của khóa luận, bao gồm: ¦ Định nghĩa tập lồi, bao lồi, điểm cực biên của bao lồi và một số tính chất cơ bản. ¦ Khái niệm đa giác đơn, tam giác phân đa giác đơn và các khái niệm liên quan. ¦ Khái niệm độ phức tạp và cách tính độ phức tạp của thuật toán. ¦ Thuật toán tăng dần tìm bao lồi. 3Chương 2. Một số tính chất của tập lồi trắc địa và bao lồi trắc địa Nội dung chính của khóa luận được trình bày trong chương này, bao gồm: ¦ Khái niệm đường trắc địa, tập lồi trắc địa, bao lồi trắc địa. Hệ thống các tính chất của tập lồi trắc địa và bao lồi trắc địa. ¦ Phát biểu và chứng minh định lý kiểu Motzkin, định lý kiểu Radon, định lý kiểu Helly-1 và kiểu Helly-2 trong mặt phẳng. ¦ Đưa ra thuật toán tìm điểm chung của một họ hữu hạn các tập lồi trắc địa trong một đa giác đơn. Kết quả trong chương này đã được công bố ở bài báo [4] và đã được tác giả báo cáo tại Hội thảo Tối ưu và Tính toán khoa học toàn quốc (Ba Vì, 20/04 - 22/04/2010). Chương 3. Thuật toán tìm bao lồi trắc địa Trong chương này, chúng tôi trình bày chi tiết thuật toán của Toussaint: ¦ Thuật toán tìm bao lồi trắc địa của một đa giác trong một đa giác đơn. ¦ Thuật toán tìm bao lồi trắc địa của một tập hợp hữu hạn điểm trong một đa giác đơn. Khóa luận được thực hiện tại trường Đại học Vinh dưới sự hướng dẫn của Thầy giáo, TS. Nguyễn Duy Bình. Tác giả xin được bày tỏ lòng biết ơn sâu sắc đến Thầy, người đã chỉ bảo tác giả một cách tận tình, chu đáo những kiến thức, kinh nghiệm trong học tập, nghiên cứu khoa học. Tác giả xin bày tỏ lòng biết ơn chân thành tới PGS. TS. Nguyễn Hữu Quang đã đóng góp nhiều ý kiến quý báu cho khóa luận. Nhân dịp này tác giả cũng xin gửi lời cảm ơn sâu sắc đến PGS. TS. Phan Thành An, TS. Nguyễn Ngọc Hải và các Thầy giáo trong Viện Toán học đã giúp đỡ tác giả trong quá trình nghiên cứu. Đồng thời, tác giả xin gửi lời cảm ơn tới Ban Chủ nhiệm khoa Toán, các thầy cô giáo trong khoa Toán đã nhiệt tình giảng dạy trong suốt quá trình học tập. Cuối cùng, xin gửi lời cảm ơn tới gia đình, người thân và bạn bè đã tạo điều kiện thuận lợi cho tác giả trong quá trình hoàn thành khóa luận. Vinh, tháng 5 năm 2010 Tác giả 4CHƯƠNG 1 KIẾN THỨC CƠ SỞ Trong chương này, chúng tôi nhắc lại các định nghĩa và một số tính chất liên quan đến: khái niệm tập lồi, bao lồi, điểm cực biên của bao lồi; khái niệm đa giác đơn, tam giác phân một đa giác đơn, hình ống tay. Đồng thời, chúng tôi trình bày một cách sơ lược khái niệm độ phức tạp của thuật toán và thuật toán tăng dần tìm bao lồi. Với mọi điểm p, q trong Rn, ta kí hiệu: [p, q] := {(1− λ)p+ λq : 0 ≤ λ ≤ 1} , ]p, q] := [p, q]\{p}, ]p, q[ := ]p, q]\{q}. 1.1 Tập lồi, bao lồi, điểm cực biên 1.1.1 Định nghĩa. ([24]) Một tập A ⊂ Rn được gọi là tập lồi nếu với mọi x1, x2 ∈ A thì đoạn thẳng [x1, x2] ⊂ A. 1.1.2 Ví dụ. Tam giác, hình tròn trong mặt phẳng; hình cầu mở B(x, r) tâm x bán kính r > 0 trong không gian Rn là tập lồi. 1.1.3 Định nghĩa. ([3]) Một tổ hợp lồi của x1, x2, ..., xk ∈ Rn là một tổng có dạng k∑ i=1 λixi, với mọi λi ≥ 0 (i = 1, k) và k∑ i=1 λi = 1. 1.1.4 Mệnh đề. ([3]) Cho A ⊂ Rn là tập lồi và các điểm x1, x2, ..., xm ∈ A. Khi đó với mọi λi > 0, m∑ i=1 λi = 1 thì tổ hợp lồi của chúng m∑ i=1 λixi ∈ A. 1.1.5 Định nghĩa. ([24]) Cho tập A trong không gian Rn. - Giao của tất cả các tập lồi chứa A gọi là bao lồi của A. Kí hiệu là convA. 5- Giao của tất cả các tập lồi đóng chứa A gọi là bao lồi đóng của A. Kí hiệu là convA. 1.1.6 Nhận xét. ([24]) (i) Bao lồi của A là tập lồi nhỏ nhất chứa A. (ii) A là tập lồi khi và chỉ khi convA = A. (iii) Bao lồi đóng của A là tập lồi đóng nhỏ nhất chứa A. 1.1.7 Mệnh đề. ([24]) Tập A lồi khi và chỉ khi A chứa tất cả các tổ hợp lồi của nó. 1.1.8 Định lý. (Định lí Caratheodory) ([3]) Bao lồi của tập A trong không gian Rn là tập tất cả các tổ hợp lồi của không quá n+ 1 điểm của A. 1.1.9 Định nghĩa. ([13]) Cho tập lồi M . Điểm x ∈ M được gọi là điểm cực biên của tập M nếu x ∈ [x1, x2];x1, x2 ∈ M thì x ≡ x1 hoặc x ≡ x2. 1.1.10 Ví dụ. Nếu M là một đoạn thẳng thì các điểm cực biên của nó là hai đầu mút, nếu M là một tam giác thì các điểm cực biên của nó là các đỉnh của tam giác, nếu M là một tứ diện thì các điểm cực biên của nó là các đỉnh của tứ diện. Chú ý rằng tập các điểm cực biên của một tập không phải bao giờ cũng hữu hạn. Chẳng hạn như khi M là một hình tròn đóng (theo chuẩn Euclide trong mặt phẳng) thì mọi điểm trên biên của nó đều là điểm cực biên của hình tròn đó. Để đơn giản hơn trong không gian R2 ta có một số dấu hiệu nhận dạng điểm cực biên như sau: 1.1.11 Nhận xét. ([13]) - Ta gọi điểm cao nhất của tập M là điểm có tung độ lớn nhất. Trong các điểm cao nhất, điểm có hoành độ lớn nhất và điểm có hoành độ nhỏ nhất là các điểm cực biên của convM . - Ta gọi điểm thấp nhất của tập M là điểm có tung độ nhỏ nhất. Trong các điểm thấp nhất, điểm có hoành độ lớn nhất và điểm có hoành độ nhỏ nhất là các điểm cực biên của convM . 6- Ta gọi điểm xa nhất về bên phải của tập M là điểm có hoành độ lớn nhất. Trong các điểm xa nhất về bên phải, điểm có tung độ lớn nhất và điểm có tung độ nhỏ nhất là các điểm cực biên của convM . - Ta gọi điểm xa nhất về bên trái của tập M là điểm có hoành độ nhỏ nhất. Trong các điểm xa nhất về bên trái, điểm có tung độ lớn nhất và điểm có tung độ nhỏ nhất là các điểm cực biên của convM . 1.2 Đa giác đơn và tam giác phân một đa giác đơn 1.2.1 Định nghĩa. ([18]) Đa giác là một miền mặt phẳng được giới hạn bởi một đường khép kín những đoạn thẳng trong mặt phẳng. Những đoạn thẳng gọi là cạnh của đa giác và những điểm chung của hai cạnh gọi là đỉnh của đa giác. Đa giác đơn là đa giác mà hai cạnh bất kì của nó hoặc không giao nhau, hoặc giao nhau tại một điểm chung duy nhất là đỉnh. Kí hiệu đa giác là [p0, p1, ..., pn], trong đó pi, ∀i = 0, n là các đỉnh, [pi, pi+1] ∀i = 0, n− 1 và [pn, p0] là các cạnh. Phần trong của đa giác P kí hiệu là int(P ), phần ngoài kí hiệu là ext(P ). 1.2.2 Định nghĩa. Cho đa giác đơn [p0, p1, ..., pn]. Ta nói thứ tự các đỉnh pi, ( i = 1, n ) của đa giác sắp xếp theo thứ tự ngược chiều kim đồng hồ nếu và chỉ nếu tiếp giáp với phần bên trái cạnh [pi, pi+1] ,∀i = 0, n− 1 và [pn, p0] là phần trong đa giác. Trong trường hợp ngược lại, ta nói các đỉnh pi của đa giác sắp xếp theo thứ tự cùng chiều kim đồng hồ. 1.2.3 Định nghĩa. ([23]) Cho xi là một đỉnh của đa giác đơn P . Ta đặt: y = λxi−1 + (1− λ)xi, z = µxi+1 + (1− µ)xi. - Nếu int [y, z] ⊂ int(P ),∀λ, µ ∈ [0; 1] thì xi được gọi là đỉnh lồi. - Nếu int [y, z] ⊂ ext(P ),∀λ, µ ∈ [0; 1] thì xi đươc gọi là đỉnh phản xạ. 7Hình 1.1: Đa giác Hình 1.2: Đa giác đơn 1.2.4 Định nghĩa. ([12]) Một đường gấp khúc 〈p0, p1, ..., pk〉 là một dãy các đoạn thẳng [pi, pi+1] với mọi i = 0, 1, ..., k− 1. Khi đó điểm pi, ∀i = 0, k được gọi là đỉnh và đoạn thẳng [pi, pi+1],∀i = 0, k − 1 được gọi là cạnh của đường gấp khúc. 1.2.5 Định nghĩa. ([18]) Cho hai điểm p, q thuộc đa giác đơn P . Ta nói rằng i) p nhìn thấy q nếu [p, q] ⊂ P . ii) p nhìn thấy rõ q nếu p nhìn thấy q và [p, q] ∩ ∂P = {p, q}, trong đó ∂P là biên của P . 1.2.6 Định nghĩa. ([18]) Cho p, q là hai đỉnh của đa giác đơn P . Khi đó p, q được gọi là đường chéo nếu p nhìn thấy rõ q. 1.2.7 Định nghĩa. ([23]) Tam giác phân một đa giác đơn P có n đỉnh, kí hiệu là T (P ), là hợp của P với tập hợp n−3 đường chéo chia P thành n−2 tam giác sao cho các đường chéo chỉ cắt nhau tại đầu mút của chúng. Nghĩa là phép tam giác phân một đa giác đơn P là dùng các đường chéo không giao nhau chia P thành các tam giác. Cho đa giác đơn P cùng với một phép tam giác phân. Trong mỗi tam giác, ta chọn một điểm đại diện (thông thường ta chọn trọng tâm của tam giác đó). Nối trọng tâm của mỗi cặp tam giác có chung cạnh, ta thu được đồ thị (cây đối ngẫu) của P tương ứng với phép tam giác phân đó, kí hiệu là T (P ). 81.2.8 Định nghĩa. ([18]) Một đa giác được gọi là hình ống tay nếu đồ thị của phép tam giác phân đa giác đó là một dãy những cạnh của đồ thị nối tiếp nhau, mà mỗi điểm nối là đầu mút của đúng hai cạnh của đồ thị đó (trừ điểm đầu và điểm cuối). Khi đó, nếu dây đó có điểm đầu là a, điểm cuối là b thì ta nói hình ống tay được xác định bởi điểm a và điểm b. Theo phép tam giác phân một đa giác và định nghĩa hình ống tay, ta có hình ống tay là một đa giác đơn. Hình 1.3: Minh họa một tam giác phân T(P) của đa giác đơn P và đồ thị của T(P) (đường đứt nét). Miền gạch chéo minh họa một ống tay 1.3 Độ phức tạp thuật toán Độ phức tạp của thuật toán là những thước đo để so sánh tính hiệu quả của thuật toán. Một thước đo hiệu quả là thời gian máy tính sử dụng để giải bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích thước xác định. Một thước đo thứ hai là bộ nhớ đòi hỏi thực hiện thuật toán đó khi giá trị đầu vào có kích thước cho trước. Gắn liền với thời gian tính toán của thuật toán là độ phức tạp thời gian và bộ nhớ là độ phức tạp không gian. Biết được độ phức tạp thời gian cho một thuật toán rất quan trọng, vì khi đó ta biết được thời gian là một phút, một năm, hay một tỉ năm để thực hiện thuật toán đó. Độ phức tạp không gian của thuật toán cho ta 9một bước chuẩn bị và thấy được khả năng đáp ứng trong việc tính toán của thuật toán. Độ phức tạp không gian gắn liền với cấu trúc dữ liệu đặc biệt dùng để tính toán trong thuật toán. Trong luận văn này chúng tôi không nghiên cứu về cơ sở dữ liệu nên ta bỏ qua độ phức tạp không gian. Để tính toán độ phức tạp của thuật toán ta chỉ xét những hàm thực f : N −→ R hầu như dương (nghĩa là tồn tại một số nguyên dương n0 sao cho f(n) > 0 với mọi n > n0) làm công cụ đo. Kí hiệu F là tập hợp tất cả các hàm như vậy. 1.3.1 Định nghĩa. ([1]) Cho hàm số g(n) ∈ F , ta định nghĩa O(g(n)) là một tập hợp tất cả các hàm f(n) ∈ F có tính chất: Tồn tại hằng số c và n0 sao cho với mọi n > n0 thì f(n) ≤ c.g(n). Nếu f(n) ∈ O(g(n)), thì ta nói rằng f(n) là Ô lớn của g(n). Ta dùng kí hiệu f(n) = g(n) +O ( h(n) ) nếu f(n)− g(n) ∈ O(h(n)). 1.3.2 Ví dụ. Nếu f(n) = 2n3 + 7n2 − 6n+ 2 thì ta có thể viết f(n) = 2n3 +O(n2). 1.3.3 Mệnh đề. ([1]) Nếu f1(n) ∈ O ( g1(n) ) và f2(n) ∈ O ( g2(n) ) thì f1(n) + f2(n) ∈ O ( g1(n) + g2(n) ) . 1.3.4 Mệnh đề. ([1]) Nếu f1(n) ∈ O ( g1(n) ) và f2(n) ∈ O ( g2(n) ) thì f1(n) + f2(n) ∈ O ( max{g1(n), g2(n)} ) . 1.3.5 Mệnh đề. ([1]) Nếu f1(n) ∈ O ( g1(n) ) và f2(n) ∈ O ( g2(n) ) thì f1(n).f2(n) ∈ O ( g1(n).g2(n) ) . 1.3.6 Mệnh đề. ([1]) Cho P (n) = akn k + ak−1nk−1 + ... + a1n + a0 là đa thức bậc k, ak > 0. Khi đó P (n) ∈ O(nk). Ta sử dụng T () cho độ phức tạp tính toán của một toán tử riêng cũng như một đoạn mã chương trình. Khi mã chương trình được tách 10 biệt rõ ràng thì ta kí hiệu độ phức tạp tính toán là T (n) (hàm biến số n, với n là số phép toán cơ sở). Độ phức tạp tính toán được đo bằng hàm O(.) là chính. Vì vậy để tính độ phức tạp tính toán của thuật toán, ta cần xác định hàm T (n) ∈ O(.) cho đoạn mã chương trình đó. Các phép tính được dùng để đo độ phức tạp thời gian có thể là phép so sánh các số nguyên, phép cộng, phép trừ, nhân, chia các số nguyên hoặc bất kì một phép toán sơ cấp nào khác. 1.3.7 Định nghĩa. ([1]) Phép tính cơ sở là phép so sánh các số nguyên, phép cộng, trừ, nhân, chia và các hàm lượng giá, hàm mũ, hàm logarit... hoặc bất kì một phép toán sơ cấp nào khác. Độ phức tạp của phép tính cơ sở là O(1). Tuy nhiên khi thực hiện tính toán với những số lớn thì phép nhân và các hàm trên cũng không là phép tính cơ sở nữa. Vì vậy với những số lớn, phép nhân và các hàm được thực hiện tính toán trên các dãy. 1.3.8 Mệnh đề. ([1]) Độ phức tạp thời gian của dãy liên tiếp các phép tính xác định bởi độ phức tạp cao nhất trong chúng. Tức là, giả sử phép tính s1 có độ phức tạp F1, phép tính s2 có độ phức tạp F2. Khi đó T (s1) ∈ O(F1); T (s2) ∈ O(F2) ⇒ T (s1, s2) ∈ max{O(F1);O(F2)}. Để dễ dàng cho việc phân tích thuật toán, người ta định ra độ phức tạp của một số phép tính trong trường hợp xấu nhất là (xem [1]): (1) Phép gán có độ phức tạp O(1). (2) Phép nhập vào thủ tục có độ phức tạp O(1). (3) Phép ra khỏi thủ tục có độ phức tạp O(1). 1.3.9 Ví dụ. ([1]) Phân tích độ phức tạp của vòng for 1. fact := 1; 2. for i := 1 to n do; 3. fact := fact+ i; 4. end for 11 Dòng 1: Phép gán cố định mất thời gian là hằng số, kí hiệu là a. Dòng 2: Với phép gán i := 1, kiểm tra i < n và i := i+1 cũng chiếm thời gian là hằng số, lần lượt kí hiệu là b; c; d. Dòng 3: Đòi hỏi thời gian cũng là hằng số, kí hiệu là e. Khi đó, thời gian (độ phức tạp) để thực hiện chương trình trên là: T (n) = a+ b+ n(c+ d) + n(e) = n(c+ d+ e) + a+ b. Điều này kéo theo T (n) ∈ O(n). Chú ý: Khi thuật toán có độ phức tạp là O(n), ta nói rằng thuật toán có độ phức tạp tuyến tính (hay được thực hiện trong thời gian tuyến tính). 1.4 Thuật toán tăng dần tìm bao lồi Ta đã biết rằng có nhiều thuật toán tăng dần tìm bao lồi, sau đây chúng tôi giới thiệu thuật toán tổng quát. Cho S = {p0, p1, ..., pn−1} là một tập hợp n điểm trong mặt phẳng. Gọi Qi−1 (i = 1, 2, ..., n− 1) là bao lồi của tập {p0, p1, ..., pi−1} ⊂ S. Việc tìm bao lồi Qi = conv{Qi−1 ∪{pi}} với i = 3, 4, ..., n− 1 được gọi là tìm bao lồi theo thuật toán tăng dần. Thuật toán Set Q2 ←− conv{p0, p1, p2} For i = 3 to n− 1 Qi ←− conv{Qi−1 ∪ {pi}}. 12 CHƯƠNG 2 MỘT SỐ TÍNH CHẤT CỦA TẬP LỒI TRẮC ĐỊA VÀ BAO LỒI TRẮC ĐỊA Trong chương này, chúng tôi trình bày một cách hệ thống các khái niệm và tính chất (có bổ sung) của đường trắc địa, tập lồi trắc địa, bao lồi trắc địa. Đồng thời, chúng tôi phát biểu và chứng minh định lý kiểu Motzkin, định lý kiểu Radon, định lý kiểu Helly-1 và kiểu Helly-2 trong mặt phẳng. Ngoài ra, chúng tôi đưa ra thuật toán tìm điểm chung của một họ hữu hạn các tập lồi trắc địa trong một đa giác đơn. 2.1 Đường trắc địa, tập lồi trắc địa, bao lồi trắc địa Trong khóa luận này ta luôn giả thiết P là một miền compact trong mặt phẳng có biên là đa giác đơn. Ta cũng nói P là một đa giác đơn. 2.1.1 Định nghĩa. ([12], [14]) Cho P là đa giác đơn và 2 điểm p, q trong P . Đường trắc địa giữa p và q, kí hiệu là GP (p, q/P ), là đường ngắn nhất (theo độ dài Euclide) nối hai điểm p và q trong đa giác P . Ngoài ra, khi viết GP (p, q/P ) là đường có hướng từ p đến q. Kí hiệu dG(p, q) là độ dài của đường trắc địa GP (p, q/P ). 2.1.2 Chú ý. ([7], [12]) Đường trắc địa GP (p, q/P ) có 2 tính chất cơ bản là: i) Nó là duy nhất. ii) Đường trắc địa là một đường gấp khúc đi qua các đỉnh là tập con của tập các đỉnh phản xạ của P . Chazelle (1982) (xem [7]); Lee và Preparata (1984) (xem [12]) đã có thuật toán tính đường trắc địa giữa hai điểm trong thời gian tuyến tính khi đa giác P đã được tam giác phân. 13 Hình 2.1: Đường trắc địa giữa p và q trong đa giác đơn P 2.1.3 Định nghĩa. Cho p và q là hai điểm phân biệt trong P . Khi đó, một điểm bóng (shadow) của GP (p, q/P ) là một điểm q thuộc biên P , mà đoạn [q, q] là kéo dài của đoạn thẳng cuối cùng của GP (p, q/P ) và nằm trong P . Tương tự, một điểm trước (foreshadow) của GP (p, q/P ) là một điểm p thuộc biên P , mà đoạn [p, p] là kéo dài về phía sau của đoạn thẳng đầu tiên của GP (p, q/P ) và nằm trong P . Đường biên trắc địa là một đường trắc địa nối hai điểm thuộc biên P . Giả sử p và q tương ứng là điểm trước gần nhất tới p và điểm bóng gần nhất tới q của GP (p, q/P ). Khi đó, đường biên trắc địa GP (p, q/P ) chia P thành hai miền đa giác bị chặn là U [p, q] và U [q, p] với phần trong của chúng tách rời nhau. Điểm của U [p, q] là ở bên phải hoặc thuộc GP (p, q/P ), còn điểm của U [q, p] là ở bên trái hoặc thuộc GP (p, q/P ). 2.1.4 Định nghĩa. ([23]) Một tập con Q trong đa giác đơn P được gọi là tập lồi trắc địa nếu GP (p, q/P ) ⊂ Q với mọi điểm p, q ∈ Q. Chú ý rằng tập lồi trắc địa được định nghĩa ở trên còn được gọi là tập lồi tương đối (trong [6] và [9]) hoặc tập P -lồi (trong [16]). Với mọi điểm p và q phân biệt của đa giác đơn P thì U [p, q] và U [q, p] là tập lồi trắc địa, nhưng chúng có thể không là tập lồi. 14 Hình 2.2: Điểm bóng q và điểm trước p của GP (p, q/P ). Miền gạch chéo là U [p, q] Hình 2.3: Q không là tập lồi trắc địa Hình 2.4: Q là tập lồi trắc địa 2.1.5 Định nghĩa. ([23]) Bao lồi trắc địa của một tập con Q trong đa giác đơn P , kí hiệu là CHG(Q/P ), là tập lồi trắc địa bé nhất chứa Q. Tập con Q trong P có thể là một đa giác, hoặc là một tập hợp điểm. 2.2 Một số tính chất của tập lồi trắc địa và bao lồi trắc địa 2.2.1 Tính chất. ([6]) Mọi tập lồi trắc địa trong một đa giác đơn P là liên thông. Một số tính chất của điểm cực biên và "chóp" của tập lồi trắc địa đã được giới thiệu trong [6]. Ta đã biết giao của tùy ý các tập lồi là tập lồi, phần trong của một tập lồi cũng là lồi (xem [24]). Ta xét các tính chất này 15 Hình 2.5: Bao lồi trắc địa của đa giác Q trong P (được biểu thị bởi đường đứt nét) Hình 2.6: Bao lồi trắc địa của tập S = {p1, p2, p3, p4} trong P (được biểu thị bởi hình gạch chéo) xem có còn đúng với tập lồi trắc địa hay không. 2.2.2 Tính chất. Giao của tùy ý khác rỗng các tập lồi trắc địa trong P là tập lồi trắc địa trong P . Chứng minh. Cho Qi, i ∈ I là các tập lồi trắc địa trong P thỏa mãn Q =⋂ i∈I Qi 6= ∅. Ta sẽ chứng minh Q là tập lồi trắc địa trong P . Thật vậy, với mọi p, q ∈ Q ta có p, q ∈ ⋂ i∈I Qi. Điều này kéo theo p, q ∈ Qi,∀i ∈ I. Vì Qi là tập lồi trắc địa trong P nên GP (p, q/P ) ⊂ Qi,∀i ∈ I. Ta suy ra GP (p, q/P ) ⊂ ⋂ i∈I Qi = Q,∀p, q ∈ Q. Vậy Q là tập lồi trắc địa trong P . 16 Từ tính chất này ta nhận thấy rằng bao lồi trắc địa của tập con Q trong đa giác đơn P là giao của tất cả các tập lồi trắc địa chứa Q. 2.2.3 Nhận xét. Phần trong của một tập lồi trắc địa có thể không liên thông, do đó theo Tính chất 2.2.1 nó có thể không là tập lồi trắc địa (minh họa bởi Hình 2.6). 2.2.4 Tính chất. Cho P là tập lồi. Tập Q là lồi trắc địa trong P khi và chỉ khi Q là tập lồi. Chứng minh. Điều kiện cần: Nếu Q là tập lồi trắc địa, ta chứng minh ∀p, q ∈ Q thì [p, q] ⊂ Q. Thật vậy: ∀p, q ∈ Q ⇒ p, q ∈ P , do P là tập lồi nên [p, q] ⊂ P , do đó GP (p, q/P ) = [p, q]. Mặt khác: do Q là tập lồi trắc địa trong P nên GP (p, q/P ) ⊂ Q, suy ra [p, q] ⊂ Q, ∀x, y ∈ Q. Vậy Q là tập lồi. Điều kiện đủ: Nếu Q là tập lồi thì ∀p, q ∈ Q ta có: [p, q] ⊂ Q ⊂ P , suy ra GP (p, q/P ) = [p, q], do đó GP (p, q/P ) ⊂ Q. Vậy Q là tập lồi trắc địa trong P . 2.2.5 Nhận xét. i) Trong trường hợp đa giác đơn P là lồi, khái niệm tập lồi trắc địa trở thành khái niệm tập lồi và bao lồi trắc địa của tập con Q trở thành bao lồi thông thường của Q. ii) Một tập lồi chính là tập lồi trắc địa trong một đa giác bất kì chứa nó. Như vậy tập lồi trắc địa là mở rộng của tập lồi. 2.2.6 Tính chất. (Bổ đề tam giác) ([6]) Cho P là một đa giác đơn và tập {x1, x2, x3} ⊂ P không suy biến. Nếu x4 ∈ U [x2, x1] ∩ U[x1, x3] ∩ U [x2, x3] thì GP (x1, x4/P ) cắt GP (x2, x3/P ). Tính chất này được minh họa trong Hình 2.7. Trong phần sau, chúng ta sẽ chỉ ra Tính chất 2.2.6 là một trường hợp đặc biệt của Định lý dạng Radon (Định lý 2.2.13). 2.2.7 Tính chất. ([16]) Cho P là một đa giác đơn và tập {x1, x2, x3} ⊂ P . Khi đó dG(x1, z) < max {dG(x1, x2), dG(x1, x3)} với mọi z ∈ GP (x2, x3/P ), z 6= x2, z 6= x3. 17 Hình 2.7: Nếu x4 ∈ U [x2, x1]∩U[x1, x3]∩U [x2, x3] (miền gạch chéo) thì GP (x1, x4/P ) cắt GP (x2, x3/P ) 2.2.8 Tính chất. ([9]) Cho P là một đa giác đơn. Nếu S1, S2 ⊂ P thì CHG(S1/P ) ⊂ CHG(S1 ∪ S2/P ). Trong Hình học tính toán, các điểm cao nhất (điểm có tung độ lớn nhất), thấp nhất (điểm có tung độ nhỏ nhất), bên trái nhất (điểm có hoành độ nhỏ nhất) và bên phải nhất (điểm có hoành độ lớn nhất) của một tập hợp phẳng hữu hạn có vai trò quan trọng trong việc tìm bao lồi của một tập hợp (xem [10] và [18]). Với bao lồi trắc địa, điều này vẫn đúng. 2.2.9 Tính chất. ([23]) Cho S là một tập hợp điểm trong đa giác đơn P và u ∈ S là điểm cao nhất (tương ứng thấp nhất, điểm bên trái nhất hoặc bên phải nhất). Trong trường hợp có nhiều điểm có cùng tung độ lớn nhất (tương ứng cùng tung độ nhỏ nhất, hoành độ nhỏ nhất hoặc hoành độ lớn nhất) thì ta sử dụng điểm bên trái nhất của điểm cao nhất (tương ứng điểm bên trái nhất của điểm thấp nhất, điểm cao nhất của điểm bên trái nhất hoặc điểm cao nhất của điểm bên phải nhất). Khi đó u thuộc biên của CHG(S/P ). Cho trước tập hợp điểm hữu hạn S nằm trong đa giác đơn P , một thuật toán tìm CHG(S/P ) sẽ được trình bày chi tiết trong chương 3. Ta đã biết các định lý cổ điển phát biểu cho tập lồi như: định lý Motzkin, định lý Radon, định lý Helly-1 và Helly-2 (xem [24]). Ta mở rộng các định lý này phát biểu cho tập lồi trắc địa. 18 2.2.10 Định lý. (Định lý kiểu Motzkin trong mặt phẳng) Cho C là tập đóng khác rỗng và lồi trắc địa trong đa giác đơn P . Khi đó, với mọi x ∈ P , tập hợp MPx,C := {z ∈ C : dG(x, z) = infu∈CdG(x, u)} chỉ chứa một phần tử (tức là tồn tại duy nhất một điểm z ∈ C mà đường trắc địa từ x tới z là ngắn nhất). Chứng minh. Vì C ⊂ P nên C là compact. Vì hàm dG(x, z) là liên tục trên C với mỗi x cố định (xem [6], trang 221) nên MPx,C 6= ∅. Bằng phản chứng ta sẽ chứng minh tập MPx,C chỉ chứa một phần tử. Giả sử với điểm x ∈ P , tồn tại hai điểm z1 ∈ C, z2 ∈ C và z1 6= z2 sao cho: d := dG(x, z1) = dG(x, z2) = infu∈CdG(x, u). Lấy z ∈ GP (z1, z2/P ); z 6= z1, z 6= z2 thì z ∈ C và do đó dG(x, z) ≥ d. (1) Mặt khác từ Tính chất 2.2.7 suy ra: dG(x, z) < max {dG(x, z1), dG(x, z2)} = d, mâu thuẫn với (1). Vậy tập MPx,C chỉ chứa một phần tử. 2.2.11 Hệ quả. (Định lý Motzkin cho tập lồi đóng trong mặt phẳng) (xem [24]) Cho ‖ . ‖ là chuẩn Euclide và C là tập lồi đóng khác rỗng trong mặt phẳng. Khi đó, với mọi điểm x trong mặt phẳng, tập hợp Mx := {z ∈ C :‖ x− z ‖= infu∈C ‖ x− u ‖} chỉ chứa một phần tử (tức là tồn tại duy nhất một điểm z ∈ C mà z gần với x nhất). Chứng minh. Lấy z1 ∈ C. Ta có: tập khác rỗng C1 := {z ∈ C :‖ x− z ‖≤‖ x− z1 ‖} là lồi và đóng. Thật vậy: C1 = B [x; ‖ x− z1 ‖] ∩ C, trong đó B [x; ‖ x− z1 ‖] là hình cầu đóng tâm x, bán kính ‖ x− z1 ‖. Do B [x; ‖ x− z1 ‖] và C là tập lồi nên C1 là tập lồi. Hơn nữa, do B [x; ‖ x− z1 ‖] và C là tập đóng nên C1 là tập đóng. Chọn một đa giác P lồi nào đó chứa C1, khi đó C1 là tập đóng và lồi trắc địa trong P . Theo Định lý 2.2.10, tồn tại duy nhất một điểm z ∈ C1 sao cho {z} ≡ MPx,C1, tức là Mx = {z}. 2.2.12 Chú ý. Tập C trong Hệ quả 2.2.11 có thể không bị chặn. 19 2.2.13 Định lý. (Định lý kiểu Radon trong mặt phẳng) Cho P là một đa giác đơn và tập S := {x1, x2, ..., xm} ∈ P . Nếu m ≥ 4 thì S có thể được chia thành 2 tập S1 và S2 (tức là S = S1∪S2;S1∩S2 = ∅) sao cho: CHG(S1/P ) ∩ CHG(S2/P ) 6= ∅. (2) Chứng minh. Giả sử p và q lần lượt là điểm trước và điểm bóng của đường trắc địa GP (p, q/P ) nối p và q trong P . Khi đó ta gọi đoạn ]p, p] và ]q, q] là đoạn mở rộng của GP (p, q/P ). Ta chứng minh kết luận của Định lý đúng với m = 4. - Nếu một điểm của S thuộc bao lồi trắc địa của ba điểm còn lại của S thì Định lý hiển nhiên đúng. - Nếu không tồn tại điểm nào của S thuộc bao lồi trắc địa của ba điểm còn lại của S: ta chỉ xét các trường hợp sau đây cho 2 đường trắc địa (một đường nối 2 điểm và đường kia nối 2 điểm còn lại của S), những trường hợp khác chứng minh tương tự. a) Đường này cắt phần mở rộng của đường kia: Không mất tính tổng quát, giả sử GP (x4, x1/P ) cắt ]x2, x2] tại x ∗ 2, ở đây x2 là điểm bóng của GP (x3, x2/P ) (minh họa bởi Hình 2.8) (trường hợp GP (x4, x1/P ) cắt ]x3, x3] ta xét tương tự). Vì x4 ∈ U [x2, x3] và U [x2, x3] là tập lồi trắc địa nên GP (x4, x3/P ) ⊂ U [x2, x3]. Vì x1 ∈ U [x3, x2] và U [x3, x2] là tập lồi trắc địa nênGP (x1, x3/P ) ⊂ U [x3, x2]. Mặt khác: x ∗ 2 ∈ GP (x4, x1/P ), do đó ta kết luận GP (x∗2, x3/P ) nằm trong miền bị chặn bởi GP (x4, x1/P ), GP (x3, x1/P ), GP (x4, x3/P ). Như vậy, x2 ∈ CHG(x1, x3, x4/P ), suy ra điều phải chứng minh. b) Đường này cắt đường kia: Không mất tính tổng quát, giả sử GP (x4, x1/P ) ∩GP (x2, x3/P ) 6= ∅. Khi đó: CHG(x4, x1/P ) ∩ CHG(x2, x3/P ) 6= ∅, vì CHG(x4, x1/P ) = GP (x4, x1/P ) và CHG(x2, x3/P ) = GP (x2, x3/P ). Do đó, S1 = {x1, x4} và S2 = {x2, x3} thỏa mãn (1). Bây giờ ta chứng minh kết luận của Định lý đúng với m > 4 bằng quy nạp theo m. 20 Hình 2.8: GP (x4, x1/P ) ∩ ]x2, x2] 6= ∅ thì S1 = {x2} và S2 = {x1, x3, x4} Giả sử Định lý đúng đếnm−1, S := {x1, x2, ..., xm} ∈ P và xm /∈ {x1, x2, ..., xm−1}. Theo giả thiết quy nạp ta có: {x1, x2, ..., xm−1} = S1∪S2 và S1∩S2 = ∅ sao cho: CHG(S1/P ) ∩ CHG(S2/P ) 6= ∅. Đặt: S ′2 = S2 ∪ {xm}. Khi đó: S = S1 ∪ S ′2 và S1 ∩ S ′2 = ∅. Hơn nữa, theo Tính chất 2.2.8 ta có: ∅ 6=CHG(S1/P ) ∩ CHG(S2/P ) ⊂ CHG(S1/P ) ∩ CHG((S2 ∪ {xm})/P ) = CHG(S1/P ) ∩ CHG(S ′2/P ). Do đó Định lý đúng đến m. Ta kết luận Định lý đúng với mọi m ≥ 4. 2.2.14 Hệ quả. (Định lý Radon trong mặt phẳng) (xem [24]) Cho tập S := {x1, x2, ..., xm} trong mặt phẳng. Nếu m ≥ 4 thì S có thể được chia thành 2 tập S1 và S2 (tức là S = S1 ∪ S2;S1 ∩ S2 = ∅ ) sao cho: convS1 ∩ convS2 6= ∅. Chứng minh. Lấy một đa giác lồi P chứa S. Khi đó, theo Định lý 2.2.13, (2) luôn đúng. Khi đó: convS1 ∩ convS2 = CHG(S1/P ) ∩ CHG(S2/P ) 6= ∅. S1 và S2 trong Định lý 2.2.13 và Hệ quả 2.2.14 được gọi là phân hoạch 21 Radon của S. 2.2.15 Định lý. (Định lý Helly-1 trong mặt phẳng) (xem [24]) Cho F là một họ các tập lồi trong mặt phẳng, F hữu hạn. Khi đó, nếu cứ 3 tập bất kì của F có ít nhất một điểm chung, thì mọi tập của F có ít nhất một điểm chung. Định lý Helly-2 trong mặt phẳng cũng được phát biểu tương tự như trên, trong đó thay giả thiết F hữu hạn bằng giả thiết F compact. Ta sẽ phát biểu hai định lý tương tự cho tập lồi trắc địa. 2.2.16 Định lý. (Định lý kiểu Helly-1 trong mặt phẳng) Cho F là một họ các tập lồi trắc địa trong một đa giác đơn, F hữu hạn. Khi đó, nếu cứ 3 tập bất kì của F có ít nhất một điểm chung, thì mọi tập của F có ít nhất một điểm chung. Chứng minh. Giả sử F := {V1, V2, ..., Vm}. Ta sẽ chứng minh kết luận của Định lý đúng với mọi m > 3 bằng quy nạp theo m. Giả sử Định lý đúng đến m− 1. Lấy xi ∈ V1 ∩ ... ∩ Vi−1 ∩ Vi+1 ∩ ... ∩ Vm. Theo Định lý 2.2.13 tập S := {x1, x2, ..., xm} có thể được chia thành hai tập S1 và S2 sao cho chúng thỏa mãn (2). Giả sử S1 := {x1, x2, ..., xk} và S2 := {xk+1, xk+2, ..., xm} (1 ≤ k < m) sao cho: x ∈ CHG(S1/P ) ∩ CHG(S2/P ). - Với i ≥ k, ta có xi ∈ Vk+1 ∩ ...∩ Vm và Vk+1 ∩ ...∩ Vm là tập lồi trắc địa. Theo Tính chất 2.2.8 ta có: x ∈ CHG(S1/P ) = CHG(x1, x2, ..., xk/P ) ⊂ Vk+1 ∩ ... ∩ Vm. - Với i ≤ k + 1, ta có xi ∈ V1 ∩ ... ∩ Vk và V1 ∩ ... ∩ Vk là tập lồi trắc địa. Theo Tính chất 2.2.8 ta có: x ∈ CHG(S2/P ) = CHG(xk+1, xk+2, ..., xm/P ) ⊂ V1 ∩ ... ∩ Vk. Do đó, x ∈ V1 ∩ V2 ∩ ...Vm, tức là mọi tập của F có ít nhất một điểm chung. 22 Định lý kiểu Helly-2 cho tập lồi trắc địa cũng được phát biểu tương tự như Định lý Helly-2. Lưu ý rằng trong mặt phẳng thì khái niệm compact tương đương với đóng và bị chặn, mà các tập lồi trắc địa nằm trong một đa giác đơn nên hiển nhiên chúng bị chặn. 2.2.17 Định lý. (Định lý kiểu Helly-2 trong mặt phẳng) Cho F là một họ các tập đóng và là lồi trắc địa trong một đa giác đơn. Khi đó, nếu cứ 3 tập bất kì của F có ít nhất một điểm chung, thì mọi tập của F có ít nhất một điểm chung. 2.3 Thuật toán tìm điểm chung của họ hữu hạn các tập lồi trắc địa trong một đa giác đơn Bài toán: Cho F = {V1, V2, ..., Vm} là một họ các tập lồi trắc địa trong đa giác đơn P . Giả sử họ F có giao khác rỗng. Ta đưa ra thuật toán tìm một điểm chung của họ F . Giả thiết là ta có sẵn một thuật toán "oracle", gọi là O, như sau: cứ 3 tập bất kì của F thì tìm được một điểm chung, hoặc là thông báo 3 tập này có giao bằng rỗng. Khi đó ta xây dựng được thuật toán tìm điểm chung của họ gồm m tập lồi trắc địa trong đa giác đơn P như sau: Input: F = {V1, V2, ..., Vm} Output: q ∈ m⋂ i=1 Vi. Thuật toán: Thuật toán được thực hiện trên ý tưởng dùng phương pháp quy nạp. Với mỗi k = 1, 2, ...,m− 2, ta tìm điểm chung của mỗi họ có dạng: {V1, V2, ..., Vk, Vt1, Vt2} , {t1, t2} ⊂ {k + 1, ...,m} (3) - Với k = 1: ta tìm được điểm chung._.