Chương 1 Kiến thức chuẩn bị Chương này hệ thống lại một số khái niệm và kết quả liên quan đến các chương tiếp theo của luận án, bao gồm các định nghĩa và tính chất liên quan đến sự định hướng của một điểm đối với một siêu phẳng có hướng; khái niệm một số điểm cực đặc biệt của một tập hợp; phát biểu bài toán tìm bao lồi cho tập hữu hạn điểm và tập hữu hạn hình tròn, trình bày một số thuật toán giải và ứng dụng tiêu biểu của chúng.1 Sự định hướng và một số kiến thức liên quan Trước khi tìm hiểu định nghĩa sự định hướng của một điểm đối với một siêu phẳng có hướng ta trình bày vắn tắt một số định nghĩa và khái niệm liên quan đến siêu phẳng và siêu phẳng tựa v. Các nội dung được tham khảo chủ yếu từ [25, 32, 43, 49]. Ta biết rằng khi cho hai điểm p, q ∈ Rd. Tập hợp tất cả các điểm x ∈ Rd có dạng x = (1 − λ)p + λq với λ ∈ R gọi là đường thẳng qua p và q , được ký hiệu là pq.
Tập hợp tất cả các điểm x ∈ Rd có dạng x = (1 − λ)p + λq với 0 ≤ λ ≤ 1 gọi là đoạn thẳng nối p với q và được ký hiệu là [p, q]. Một siêu phẳng (hyperplane), được cho bởi H = {x ∈ Rd : ha, xi = α, a ∈ Rd \ {0}}, α ∈ R, được gọi là một siêu phẳng tựa (supporting hyperplane) của tập lồi đóng S nếu H ∩ S 6= ∅ và S nằm ở một trong hai nửa không gian đóng được phân chia bởi H. Nửa không gian đó được gọi là nửa không gian tựa (supporting half-space) của S. Nửa không gian tựa của S bao gồm cả siêu phẳng tựa H được gọi là nửa không gian tựa đóng.
13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1. Một tập đa diện đóng (closed polyhedral set) S (S 6= ∅ và S 6= Rd ) là giao của một họ hữu hạn những nửa không gian tựa đóng. Một đa diện lồi là một tập đa diện đóng và bị chặn. Cho H là một siêu phẳng tựa của một tập lồi S.
Khi đó H ∩ S được gọi là một diện (face) của S. Mỗi diện F của S là giao của hai tập lồi nên nó là một tập lồi. Một diện F là một diện thực sự (proper) của S nếu F 6= ∅ và F 6= S. Hai diện không thực sự (improper face) của S là tập rỗng ∅ (dim ∅ = −1) và chính tập S (dim S = d).
Nếu dim F = k thì 0 ≤ k ≤ d − 1 và khi đó F được gọi là một k -diện của S. Cho R ⊆ Rd là một đa diện lồi với phần trong khác rỗng và dim R = d. Tiếp theo ta trình bày một khái niệm quan trọng được sử dụng trong hầu hết các thuật toán tìm bao lồi, đó là khái niệm sự định hướng của một điểm đối với một siêu phẳng có hướng. Một siêu phẳng có hướng (oriented hyperplane), cũng có thể được gọi là siêu phẳng định hướng, (x1 x2.
xd ) là một siêu phẳng chứa d điểm độc lập affin x1 , x2 ,. , xd trong không gian Rd với thứ tự các điểm được hiểu theo nghĩa là (x1 x2. Trong Rd , cho trước d điểm độc lập affin xi = (xi1 , xi2 ,. td 1 Định nghĩa 1.
Điểm t được gọi là ở phía dương (tương ứng ở phía âm, thuộc) siêu phẳng (x1 x2. xd ) nếu orient(x1 , x2. xd , t) > 0 (tương ứng, orient(x1 , x2 ,. 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
td 1 d+1 X = (−1)d+1+j tj |Md+1,j |, j=1 trong đó |Md+1,j | là định thức con của orient(x1 , x2 ,. , xd , t) được xác định bằng cách bỏ dòng thứ d + 1 và cột thứ j. Nếu đặt νj = (−1)d+1+j |Md+1,j |, j = 1, 2,. , xd là các điểm cố định, t là một điểm thay đổi thì νd+1 là một hằng số không phụ thuộc vào t.
, zd ) là điểm bất kỳ thuộc siêu phẳng (x1 x2. xd ) thì orient(x1 , x2 ,. Khi đó ta có d X νd+1 = − νi zi .4) i=1 Do đó d d d → − νi zi = → − X X X 1 2 d orient(x , x ,. , x , t) = νi ti + νd+1 = νi ti − ν zt.5) i=1 i=1 i=1 Dễ dàng thấy rằng biểu thức orient có dạng một phương trình siêu phẳng qua d điểm x1 , x2 ,.
, xd với vector pháp tuyến là → − ν = (ν1 , ν2 ,. , νd ) và hệ số tự do d νi zi. Tức là, siêu phẳng định hướng (x1 x2. xd ) có phương trình P là νd+1 = − i=1 d X νi xi + νd+1 = 0.6) i=1 Để thuận tiện cho các nội dung và quy ước sử dụng ký hiệu ở các chương tiếp theo, chúng tôi đưa ra định nghĩa nửa không gian dương, nửa không gian âm của một siêu phẳng định hướng được xác định bởi vector định hướng dương cho trước.
15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1. Gọi H là siêu phẳng định hướng có phương trình cho bởi (1.6) với vector → − ν được xác định bởi (1. Nửa không gian dương của H , ký hiệu bởi H + , được định nghĩa là nửa không gian nằm ở phía dương và bị chặn bởi siêu phẳng H. Nửa không gian mở còn lại được gọi là nửa không gian âm của H , ký hiệu bởi H −.
Vector →− ν được gọi là một vector định hướng dương của siêu phẳng định hướng H. Từ Định nghĩa 1.5 và công thức (1.5) ta nhận thấy rằng nếu z là một điểm bất kỳ của H và một điểm t nằm ở không gian dương H + → − → − thì → − ν zt > 0, điểm t nằm ở nửa không gian âm H − thì → − ν zt < 0, điểm t thuộc → − → − H nếu ν zt = 0.2 Bài toán tìm bao lồi và ứng dụng Sau đây ta trình bày định nghĩa bao lồi, bài toán tìm bao lồi của một tập hữu hạn điểm và bài toán tìm bao lồi cho tập hữu hạn đường tròn. Bao lồi của một tập S là giao của tất cả các tập lồi chứa S. Ta ký hiệu bao lồi của S là conv(S).
Mỗi p ∈ S thỏa mãn p ∈ / conv(S\{p}) được gọi là một điểm cực biên của tập S hay còn được gọi là đỉnh của conv(S). Tiếp theo ta đưa ra định nghĩa các điểm cực đặc biệt của một tập điểm trong R2. Việc tìm các điểm này thường là bước đầu tiên trong các thuật toán tìm bao lồi. Cho P là một tập hữu hạn điểm trong không gian R2.
Trong các điểm của P có tung độ y lớn nhất thì điểm có hoành độ x nhỏ nhất được gọi là điểm tận cùng trên trái. Tương tự ta định nghĩa được bảy điểm cực còn lại.1, q1 là điểm tận cùng trái trên, q2 là điểm tận cùng trên trái, q3 là điểm tận cùng trên phải, q4 là điểm tận cùng phải trên, q5 là điểm tận cùng phải dưới, q6 là điểm tận cùng dưới phải, q7 là điểm tận cùng dưới trái và q8 là điểm tận cùng trái dưới.1 Bài toán tìm bao lồi cho tập hữu hạn điểm Từ định nghĩa của bao lồi ta dễ dàng thấy rằng bao lồi của tập P là tập lồi nhỏ nhất chứa P. Bao lồi của một tập hữu hạn điểm P ⊂ Rd là một đa diện 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Các điểm cực đặc biệt. lồi trong Rd (xem [32], tr.
Một đa diện lồi chỉ có hữu hạn các diện rời nhau, mỗi diện cũng là một đa diện lồi. Như vậy, bài toán tìm bao lồi của tập P là bài toán xác định tất cả các diện của conv(P ) với một thứ tự mà theo đó ta có thể dựng lại được conv(P ). Ta có dữ liệu đầu vào của bài toán là tập hợp P hữu hạn gồm n điểm p1 , p2 ,. , pn và đầu ra là tập các diện của bao lồi conv(P ) (Hình 1.2 Bao lồi của tập điểm trong Hình 1.3 Bao lồi của tập điểm trong không gian R2 .1 Một số thuật toán tìm bao lồi trong R2 Có nhiều các thuật toán tìm bao lồi được đề xuất kể từ đầu những năm 70.
Trong mục này ta nhắc lại một số thuật toán tiêu biểu tìm bao lồi của tập hữu hạn điểm trong không gian hai chiều. Thuật toán gói quà Một trong những thuật toán đơn giản nhất trong các thuật toán hình học phẳng là thuật toán gói quà. Thuật toán này phát hiện độc lập bởi D. 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chand và S.
Kapur vào năm 1970 [16] và R. Cho tập P hữu hạn n điểm, thuật toán bắt đầu với i = 1, ta xác định một điểm thuộc bao lồi, chẳng hạn ta chọn điểm v1 là điểm tận cùng ở phía âm dưới và đưa điểm v1 vào tập đỉnh của bao lồi. Sau đó ta tìm điểm vi sao cho tất các điểm còn lại của P đều nằm ở phía dương đoạn thẳng v1 vi. Nếu tìm được nhiều hơn một điểm vi sao cho tất cả các điểm còn lại của P đều nằm ở phía dương hoặc nằm trên v1 vi thì trong các điểm đó ta chọn điểm xa v1 nhất và đưa điểm đó vào tập đỉnh của bao lồi.
Ta có thể lặp lại điều này để tìm ra các điểm tiếp theo, đến khi nào tìm được điểm trùng với v1 thì dừng lại. Như vậy để tìm mỗi điểm mới của bao lồi ta mất thời gian là O(n). Do vậy thuật toán này có độ phức tạp tính toán là O(nh), trong đó h là số đỉnh của bao lồi. Trong trường hợp xấu nhất, độ phức tạp của thuật toán là O(n2 ) khi h = n.
Thuật toán quét Graham Thuật toán quét Graham (Graham scan) là một thuật toán phức tạp hơn thuật toán gói quà được phát hiện bởi R. Giả sử cho tập hợp điểm P bất kỳ, đầu tiên thuật toán sắp xếp lại các điểm của tập hợp này theo một thứ tự xác định. Việc sắp xếp hoàn thành có độ phức tạp tính toán là O(n log n) và cho ta một đa giác khép kín. Đa giác này có thể không lồi nhưng ta có thể dựa vào nó để tìm tập H các đỉnh của bao lồi conv(P ).