Luận văn thạc sĩ bài toán tìm bao lồi

  • Số trang: 54 |
  • Loại file: PDF |
  • Lượt xem: 27 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN KIỀU LINH BÀI TOÁN TÌM BAO LỒI LUẬN VĂN THẠC SỸ Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 00 00 00 Giáo viên hướng dẫn: TS. HOÀNG NAM DŨNG THÁI NGUYÊN, 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn thành luận văn tốt nghiệp thạc sỹ của mình. Để có được kết quả này, tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến thầy tôi, TS. Hoàng Nam Dũng, người đã định hướng nghiên cứu cho tôi trong suốt thời gian thực hiện luận văn của mình. Cám ơn thầy đã mang đến cho tôi những bài học quý báu về phương pháp nghiên cứu khoa học. Đó chính là nền tảng cơ bản, là những hành trang vô cùng quý giá để tôi có thể tiếp cận được với khoa học thật sự. Thầy đã dạy cho tôi không chỉ những kiến thức khoa học mà còn cả những bài học về cuộc sống, về tình người. Xin cảm ơn về tất cả những gì thầy đã mang đến cho tôi. Tôi xin gửi lời cảm ơn chân thành tới các thầy cô ở trường Đại học Khoa học, Đại học Thái Nguyên và các thầy cô ở Viện Toán học đã luôn tận tình giúp đỡ, theo dõi và động viên cho tôi trong suốt quá trình thực hiện luận văn này. Xin cám ơn những người thân trong gia đình đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và hoàn thành những công việc của mình. Xin cám ơn tất cả những người bạn thân yêu, những người đã yêu mến, chia sẻ với tôi những khó khăn vui buồn trong khi tôi thực hiện luận văn này. 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục 1 Bài toán tìm bao lồi và ứng dụng 1.1 Bài toán tìm bao lồi . . . . . . . . . . . . . . . . 1.1.1 Tập lồi . . . . . . . . . . . . . . . . . . . 1.1.2 Bao lồi . . . . . . . . . . . . . . . . . . . 1.1.3 Bài toán tìm bao lồi . . . . . . . . . . . 1.2 Ứng dụng của bài toán tìm bao lồi . . . . . . . 1.2.1 Nhận dạng . . . . . . . . . . . . . . . . . 1.2.2 Tìm đường đi ngắn nhất . . . . . . . . . 1.2.3 Hệ thống thông tin địa lý (GIS) . . . . 1.2.4 Thống kê . . . . . . . . . . . . . . . . . . 1.2.5 Tìm đường kính của một tập hợp điểm 2 Các 2.1 2.2 2.3 thuật toán tìm bao lồi Một số khái niệm và thuật toán cơ bản . Thuật toán gói quà . . . . . . . . . . . . Thuật toán quét Graham . . . . . . . . . 2.3.1 So sánh hai góc trong mặt phẳng 2.3.2 Sắp xếp . . . . . . . . . . . . . . . 2.3.3 Thuật toán quét Graham . . . . 2.4 Thuật toán Quickhull . . . . . . . . . . . 2.5 Thuật toán Chan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 7 7 9 9 10 11 12 14 15 . . . . . . . . 19 19 22 23 24 25 29 30 35 3 Cải tiến các thuật toán 39 3.1 Xóa điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Cải tiến thuật toán Quickhull . . . . . . . . . . . . . . . . . . . . . 41 4 Kết quả tính toán 45 4.1 Tạo tập hợp điểm ngẫu nhiên và thuật toán xóa điểm . . . . . . . 45 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4.2 Các kết quả tính toán . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Bài toán tìm bao lồi là một trong những bài toán đặc biệt quan trọng trong lĩnh vực hình học tính toán bởi các ứng dụng đa dạng của nó. Chẳng hạn như nhận dạng mẫu, xử lý hình ảnh, tìm đường đi cho robot, số liệu thống kê, . . . . Hơn nữa bài toán tìm bao lồi còn được áp dụng để tìm ra các bài toán tính toán hình học khác như tìm tam giác phân Delaunay, tìm đường kính của một tập hợp, tìm các lớp lồi của một tập hợp, . . . . Vì các ứng dụng quan trọng của nó nên nhiều nhà khoa học đã bắt tay vào việc nghiên cứu và đưa ra các thuật toán tìm bao lồi của một tập hợp. Điển hình như sự phát hiện của Chand và Kapur vào năm 1970 và Jarvis vào năm 1973 với thuật toán gói quà, Ronald Graham vào năm 1972 với thuật toán quét Graham, W. Eddy năm 1977 và A.Bykat năm 1978 với thuật toán Quickhull, Timothy Chan vào năm 1993 với thuật toán Chan, . . . . Hiện nay có rất nhiều nhà khoa học dựa vào các thuật toán này để cải tiến và tăng tốc cho chúng nhằm đáp ứng các yêu cầu của cuộc sống hiện đại như xử lí các vấn đề ở tốc độ cao với số lượng lớn. Xuất phát từ lí do trên luận văn này đưa ra một một số cải tiến nhằm tăng tốc cho việc tính toán khi tìm bao lồi của một tập hợp điểm trên mặt phẳng. Luận văn này gồm bốn chương. Chương 1 phát biểu bài toán tìm bao lồi và trình bày một số ứng dụng quan trọng của bài toán này trong thực tiễn. Chương 2 trình bày các thuật toán tìm bao lồi trong không gian hai chiều như thuật toán gói quà, thuật toán quét Graham, thuật toán Quickhull và thuật toán Chan. Chương 3 đưa ra thuật toán xóa điểm, là thuật toán dựa vào tính chất của những điểm cực nằm trong tập các đỉnh của bao lồi, để xóa bớt những điểm nằm trong đa giác tạo bởi các điểm cực, nhằm mục đích giảm bớt số lượng các điểm đầu vào cho các thuật toán tìm bao lồi. Đồng thời chương này cũng trình bày một cải tiến cho thuật toán Quickhull. Chương 4 nêu các kết quả tính toán của các thuật toán đã được trình bày ở chương 3 như thuật toán xóa điểm, thuật toán Quickhull và Quickhull cải tiến. Trong quá trình nghiên cứu và tìm tòi để hoàn thành luận văn này, mặc dù 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tác giả đã có nhiều nỗ lực cố gắng, nhưng chắc chắn luận văn sẽ không tránh khỏi những thiếu sót. Tác giả rất mong nhận được sự góp ý của các thầy cô và các bạn để luận văn được hoàn thiện hơn. 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 Bài toán tìm bao lồi và ứng dụng Như đã biết, bài toán tìm bao lồi là một trong những bài toán đặc biệt quan trọng trong lĩnh vực hình học tính toán. Chương này phát biểu bài toán tìm bao lồi và đưa ra một số ứng dụng quan trọng của bài toán trong thực tế. 1.1 Bài toán tìm bao lồi Trước khi trình bày định nghĩa bài toán tìm bao lồi ta trình bày các khái niệm tập lồi, tổ hợp lồi, . . . [19]. 1.1.1 Tập lồi Định nghĩa 1.1. Cho hai điểm p, q ∈ Rn . Tập hợp tất cả các điểm x 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à pq . Định nghĩa 1.2. Cho p1 , p2 , ..., pk ∈ Rn . Những điểm x ∈ Rn có dạng x = k P λi pi i=1 trong đó pi ∈ Rn và 0 ≤ λi ≤ 1 với p1 , p2 , ..., pk ∈ Rn . k P λi = 1 được gọi là một tổ hợp lồi của i=1 Định nghĩa 1.3. Một tập S được gọi là một tập lồi nếu cho hai điểm p, q tùy ý thuộc S thì bất kì tổ hợp lồi nào của p và q cũng nằm trong S hay đoạn thẳng pq phải nằm hoàn toàn trong S (hình 1.1). 1.1.2 Bao lồi Sau đây ta trình bày định nghĩa bao lồi và phát biểu bài toán tìm bao lồi trong không gian Rn bất kỳ. 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (a) Tập lồi (b) Tập không lồi Hình 1.1 Định nghĩa 1.4. Bao lồi của một tập S hữu hạn điểm 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) (hình 1.2). Nhận xét 1.1. Bao lồi của tập S là tập lồi nhỏ nhất chứa S . Bao lồi của một tập hữu hạn điểm P ⊂ Rn là một đa diện lồi trong Rn (hình 1.3). Định nghĩa 1.5. Mỗi p ∈ P thỏa mãn p ∈ / conv(P \{p}) được gọi là một đỉnh của conv(P ). Hình 1.2 Bao lồi của một tập hữu hạn Hình 1.3 Bao lồi của một tập hữu hạn 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Nhận xét 1.2. Nếu gọi tập hợp các đỉnh của conv(P ) là H thì ta có conv(P ) = conv(H). Định nghĩa 1.6. Trong mặt phẳng, đa giác tạo bởi các đỉnh của một bao lồi được gọi là biên của bao lồi đó. 1.1.3 Bài toán tìm bao lồi Cho một tập hợp P hữu hạn điểm, bài toán tìm bao lồi của P là bài toán tìm tập hợp H các đỉnh của bao lồi conv(P ) của P . Input: Tập hợp P hữu hạn n điểm p1 , p2 , ..., pn . Output: Tập đỉnh của bao lồi conv(P ), H = {h1 , h2 , ..., hm }(hình 1.4). (a) Input (b) Output Hình 1.4 1.2 Ứng dụng của bài toán tìm bao 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 có ứng dụng đa dạng trong nhiều lĩnh vực chẳng hạn như nhận dạng mẫu, xử lý hình ảnh, tìm đường đi cho robot, số liệu thống kê, . . . . Bài toán tìm bao lồi còn được áp dụng rộng rãi để tìm ra các bài toán tính toán hình học khác và các bài toán này có rất nhiều ứng dụng trong thực tế như bài toán tìm tam giác phân Delaunay, bài toán tìm đường kính của một tập hợp, bài toán tìm các lớp lồi của một tập hợp, . . . . Sau đây ta sẽ trình bày một số ứng dụng quan trọng của bài toán tìm bao lồi. 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.1 Nhận dạng Bài toán tìm bao lồi có ứng dụng rất quan trọng trong lĩnh vực nhận dạng. Nhận dạng nhằm mục đích phân loại dữ liệu (là các mẫu) dựa vào thông tin thống kê được khai thác từ các mẫu có sẵn. Các mẫu cần phân loại thường được biểu diễn thành các nhóm của các dữ liệu đo đạc hay quan sát được. Các ứng dụng phổ biến trong thực tế là nhận dạng tiếng nói tự động, phân loại văn bản thành nhiều loại khác nhau (ví dụ những thư điện tử spam/nonspam), nhận dạng tự động các mã bưu điện viết tay trên các bao thư, hay hệ thống nhận dạng mặt người, nhận dạng biển số xe, . . . . Sau đây ta xét một ứng dụng cụ thể của bài toán tìm bao lồi trong nhận dạng biển số xe. Nội dung và hình vẽ được trích trong [14]. Hình 1.5 Quy trình của quá trình xử lý nhận diện biển số xe thường thông qua các bước như hình 1.5 và bài toán tìm bao lồi được ứng dụng trong bước 4 của quá trình nhận dạng. Trong bước này ta cô lập từng kí tự trong biển số xe được trích ra ở bước 3. Tiếp theo sử dụng thuật toán tìm bao lồi tìm vùng tối thiểu chứa mỗi kí tự đó để chuẩn bị tiến hành nhận dạng ở bước 5. Hình 1.6 biểu diễn các 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn bước của quá trình xử lý nhận diện biển số xe. (a) Chụp ảnh từ camera (b) Tiền xử lý ảnh (c) Trích vùng biển số xe (d) Tìm bao lồi cho mỗi kí tự Hình 1.6 1.2.2 Các bước của quá trình nhận dạng Tìm đường đi ngắn nhất Bài toán đặt ra là tìm một đường đi ngắn nhất cho một robot đi từ điểm s đến điểm t với các chướng ngại vật nằm giữa hai điểm đó. Giả sử để tránh các chướng ngại vật thì robot không thể đi xuyên qua chúng được. Vì vậy nếu ta tìm được bao lồi của tập P ∪ {s, t}, với P là tập các chướng ngại vật, thì đi theo đường ngắn hơn trong hai đường biên trên và biên dưới của bao lồi sẽ không gặp các chướng ngại vật và đường đi ấy là ngắn nhất (hình 1.7). Hình 1.7 Đường đi ngắn nhất 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.3 Hệ thống thông tin địa lý (GIS) Bài toán tìm bao lồi được ứng dụng trong các mô hình biểu diễn dữ liệu của hệ thống thông tin địa lý GIS. GIS được thiết kế như một hệ thống chung để quản lý dữ liệu không gian, nó có rất nhiều ứng dụng trong việc phát triển đô thị và môi trường tự nhiên như là quy hoạch đô thị, quản lý nhân lực, nông nghiệp, điều hành hệ thống công ích, lộ trình, nhân khẩu, bản đồ, giám sát vùng biển, cứu hoả, bệnh tật, . . .. Các ứng dụng này của GIS được trình bày cụ thể trong [2]. Trong các mô hình biểu diễn dữ liệu của GIS, chúng ta thường nhắc đến một khái niệm là feature. Feature là một đối tượng trên bản đồ có hình dạng, vị trí và các thuộc tính xác định cụ thể. Có ba mô hình dữ liệu trong GIS như mô hình dữ liệu vector, mô hình dữ liệu raster và mô hình TIN. Bài toán tìm bao lồi được áp dụng một cách gián tiếp trong các mô hình dữ liệu vector và mô hình dữ liệu TIN. Dưới đây ta trình bày ứng dụng cụ thể của bài toán tìm bao lồi trong mô hình dữ liệu vector. Nội dung và các hình vẽ trong phần này trích từ [10]. Mô hình dữ liệu vector xem các sự vật và hiện tượng là tập các thực thể không gian cơ sở và tổ hợp của chúng (hình 1.8a). Trong mô hình 2D thì các thực thể cơ sở bao gồm: điểm (points), đường (lines) và vùng (polygons). Đối tượng điểm biểu diễn các feature không có miền bao hay độ dài, nhiều khi nó biểu diễn các feature có kích thước quá nhỏ so với tỷ lệ của bản đồ (hình 1.8b). Đối tượng đường dùng để biểu diễn các feature có chiều dài xác định nhưng không có miền bao hay những feature rất hẹp so với tỷ lệ bản đồ (hình 1.8c). Đối tượng vùng được dùng để biểu diễn các feature có miền bao xác định như ruộng đất, ao, hồ hay các đơn vị hành chính, . . . (hình 1.8d). Sau đó dựa vào các thuật toán phân tích trên mô hình dữ liệu vector để đưa tập thực thể cơ sở thành một tập đối tượng có thể đưa vào bản đồ. Một trong các thuật toán này là thuật toán tìm bao lồi. Khi các thực thể cơ sở nhận được dưới dạng điểm thì ta dùng thuật toán tìm bao lồi của một tập hợp điểm để đưa ra một một đối tượng là một đa giác lồi nhỏ nhất chứa các điểm đó (hình 1.9a). Khi các thực thể cho dưới dạng đường thì thuật toán tìm bao lồi của đường cong trong mặt phẳng, thuật toán này được trình bày cụ thể ở [12], cũng cho ta một đối tượng mới là một đa giác lồi nhỏ nhất chứa các thực thể đó (hình 1.9b). Cuối cùng nếu đối tượng được cho dưới dạng vùng thì ta phải áp dụng thuật toán tìm bao lồi cho miền đa giác đơn, thuật toán này đươc trình bày trong [9], để tạo ra một đối tượng mới là 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn một vùng nhỏ nhất bao kín đối tượng. Những đối tượng mới này có tính chất, hình dạng và kích thước gần với các tập thực thể cơ sở nhất. Do vậy những đối tượng này phù hợp để đưa vào bản đồ (hình 1.9). (a) Bản đồ với mô hình dữ liệu vector. (b) Đối tượng điểm trên bản đồ. (c) Đối tượng đường trên bản đồ. (d) Đối tượng vùng trên bản đồ. Hình 1.8 (a) Thuật toán tìm bao lồi cho đối tượng điểm. (b) Thuật toán tìm bao lồi cho đối tượng đường. (c) Thuật toán tìm bao lồi cho đối tượng vùng. Hình 1.9 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.4 Thống kê Như ta biết, một bài toán trọng tâm trong thống kê là ước lượng đánh giá thông số dân số (population parameter) từ một mẫu dữ liệu ngẫu nhiên được rút ra. Tuy nhiên một số thông số đó lại cực kỳ nhạy cảm với giá trị ngoại lai (outliers), đó là những điểm có số liệu cách xa một cách bất thường với trung tâm của các quan sát. Các giá trị ngoại lai có thể có ảnh hưởng lớn đến việc tính toán các ước lượng thông số trong phân tích hồi quy (regression analysis) hoặc các số thống kê tóm tắt (brief statistics) chẳng hạn như trung bình và phương sai mẫu mà kết quả là có thể lấy cả những giá trị không tiêu biểu. Do đó các giá trị ngoại lai thường hay bị bỏ qua để không gây ra lỗi trong dự đoán. Một ứng dụng của bao lồi có thể giải quyết được vấn đề này, đó là thuật toán tìm các lớp lồi của một tập hợp bất kỳ. Với đầu vào là các điểm của một mẫu dữ liệu ngẫu nhiên, ta có thể sử dụng thuật toán này cho vấn đề xóa lớp lồi đến khi loại bỏ được các giá trị ngoại lai và giữ lại phần gần với trung tâm của các quan sát hơn. Sau đây chúng ta đi trình bày thuật toán tìm các lớp lồi của một tập hợp điểm. Nội dung của phần này tham khảo trong [3]. Giả sử ta có tập P , biên của conv(P ) được gọi là lớp lồi đầu tiên của P , kí hiệu là cl(1). Nếu chúng ta xóa những điểm nằm trên cl(1) và tìm một bao lồi mới của những điểm còn lại ta sẽ nhận được lớp lồi thứ hai của P , kí hiệu là cl(2). Như vậy chúng ta sẽ tìm được lớp lồi thứ i + 1 sau khi loại bỏ những điểm của lớp lồi thứ i. Đây chính là nội dung của bài toán tìm các lớp lồi của một tập hợp. Từ đó ta có định nghĩa độ sâu của một điểm trong một tập P như sau. Định nghĩa 1.7. Độ sâu của một điểm p trong một tập P bằng số lớp lồi được bỏ đi từ tập P trước khi p bị loại bỏ. Độ sâu của một tập P là độ sâu của điểm sâu nhất của nó, tức là độ sâu của điểm cuối cùng bị loại bỏ. Độ sâu của tập P kí hiệu là depth(P ) (hình 1.10). Trong hình 1.10, pi có độ sâu là i với i = 0, 1, 2, 3, 4. Phương pháp tốt nhất để tìm bao lồi của một tập P gồm n điểm có độ phức tạp tính toán của thuật toán là O(n log n). Định nghĩa độ phức tạp tính toán của thuật toán được trình bày cụ thể ở chương 2. Đầu tiên ta loại bỏ các đỉnh của lớp lồi thứ nhất, sau đó tiếp tục tìm bao lồi của các tập điểm còn lại. Do đó để tìm được độ sâu depth(P ) của P thì độ phức tạp tính toán của thuật toán là O(n2 log n). Tuy nhiên áp dụng thuật toán gói quà tại mỗi lớp lồi cho ta một thuật toán có độ phức tạp tính toán tốt hơn. Giả sử hi là số đỉnh của lớp lồi thứ i. Tại lớp lồi thứ i thì thuật toán gói quà có độ phức tạp là O(nhi ) và do đó 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn độ phức tạp của thuật toán tìm các lớp lồi là O(nh0 + nh1 + nh2 + ... + nhk ) với k là độ sâu của tập điểm đầu vào. Vì h0 + h1 + h2 + ... + hk = n nên độ phức tạp của thuật toán này là O(n2 ). 1.2.5 Tìm đường kính của một tập hợp điểm Bài toán tìm đường kính của một tập hợp điểm là một bài toán rất quan trọng trong hình học tính toán và có ứng dụng trong những bài toán phân cụm (clustering), đây là bài toán làm việc với các nhóm đối tượng tương tự nhau được trình bày cụ thể ở [17], trang 170. Trước khi trình bày thuật toán của bài toán tìm đường kính của một tập hợp điểm ta có định nghĩa sau. Định nghĩa 1.8. Cho một tập S có n điểm, tìm trong tập S một cặp điểm sao cho khoảng cách (khoảng cách Euclid) giữa chúng là lớn nhất. Nếu có nhiều cặp điểm như vậy thì ta chọn một cặp trong số đó. Độ dài cạnh nối cặp điểm xa nhất được gọi là đường kính của tập hợp S và cặp điểm xa nhất đó được gọi là hai đỉnh của đường kính. Như vậy bài toán tìm đường kính của một tập hợp là bài toán tìm cặp điểm xa nhất của tập hợp đó. Phương pháp có thể áp dụng giải bài toán này là ta đi tìm tất cả các khoảng cách giữa hai điểm bất kỳ của tập S và đường thẳng nối một trong những cặp điểm có khoảng cách lớn nhất là đường kính của một tập hợp điểm. Cách làm này có độ phức tạp tính toán là O(n2 ). Tuy nhiên dưới đây ta sẽ trình bày một phương pháp là ứng dụng của bao lồi với độ phức tạp tính toán là O(n log n). Mệnh đề 1.1. Cho tập S gồm n điểm trong mặt phẳng. Hai đỉnh đường kính của tập S là hai điểm cực biên của S , tức là hai điểm đó phải là hai đỉnh của Hình 1.10 Độ sâu của một điểm và các lớp lồi của một tập hợp. 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hình 1.11 bao lồi conv(S). Chứng minh. Bây giờ ta giả sử rằng một đỉnh của đường kính không phải là điểm cực biên của S. Gọi (d, a) là cặp điểm xa nhất và giả sử rằng a không phải là điểm cực biên của S . Khi đó a phải nằm trong tam giác dcb nào đó (tính cả biên) với c, b ∈ S . Từ hình 1.11 ta thấy rõ ràng rằng độ dài đoạn thẳng da, kí hiệu |da|, nhỏ hơn độ dài đoạn thẳng da0 , kí hiệu |da0 |. Và vì |da0 | < max{|db|, |dc|} nên |da| < max{|db|, |dc|}. Điều này mâu thuẫn với giả sử da là đường kính của tập hợp S . Định nghĩa 1.9. Cho tập S gồm n điểm, nếu đường thẳng l đi qua một hay nhiều điểm của tập S sao cho tập hợp S nằm hoàn toàn trong một nửa mặt phẳng xác định bởi đường thẳng l thì l được gọi là đường thẳng tựa trên tập S . Định nghĩa 1.10. Nếu l1 và l2 là hai đường thẳng tựa trên tập S tương ứng đi qua p1 và p2 (p1 , p2 ∈ S ) và l1 song song với l2 thì cặp điểm (p1 , p2 ) được gọi là cặp điểm đối cực của S. Dưới đây ta đưa ra một định lí đã được trình bày và chứng minh ở [17]. Định lý này đưa ra một ý tưởng quan trọng cho thuật toán tìm cặp điểm xa nhất của một tập điểm trong mặt phẳng. Định lý 1.1. ([17], định lý 4.18, trang 17) Cặp điểm xa nhất của một tập S là một cặp đối cực của S mà có khoảng cách lớn nhất. 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Như vậy để tìm cặp điểm xa nhất thì ta phải tìm tất cả các cặp đối cực và chọn một cặp có khoảng cách lớn nhất. Từ mệnh đề 1.1 và định lý 1.1 thì tất cả các cặp điểm đối cực phải nằm trên bao lồi của tập S . Do đó đầu tiên ta phải tìm bao lồi của của tập S , sau đó xác định các cặp đối cực từ các đỉnh của bao lồi và tìm ra cặp có khoảng cách xa nhất. Thuật toán tìm cặp điểm xa nhất có thể được trình bày như Algorthm 1. (a) (b) Hình 1.12 Ta có sự phân tích độ phức tạp tính toán của Algorithm 1 như sau. Bước (1) có độ phức tạp là O(n log n). Xét đến bước (2), (a) có độ phức tạp là O(h), (b) - (d) lặp lại như bước (a) cho mỗi cặp đối cực nên cũng có độ phức tạp là O(h). Cuối cùng (e) cũng có độ phức tạp là O(h). Vì tập S có n điểm nên bao lồi conv(S) có nhiều nhất n đỉnh, khi đó trong trường hợp xấu nhất thì bước (2) có độ phức tạp là O(n). Do đó bài toán tìm đường kính của một tập hợp điểm có độ phức tạp tính toán là O(n log n). 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Algorithm 1 Thuật toán tìm cặp điểm xa nhất của một tập hợp 1. Tìm bao lồi của tập S. 2. Cho H = {p0 , p1 , ..., ph } là các đỉnh của bao lồi conv(S). Giả sử bước 1 cho các đỉnh của bao lồi sắp xếp theo thứ tự ngược chiều kim đồng hồ. Ta tìm tất cả các cặp đối cực bằng cách quét tròn một đường thẳng quanh các đỉnh của bao lồi, cụ thể như sau. (a) Cho l1 là đường thẳng tựa của S xác định bởi hai điểm p0 và p1 thuộc H. Với mọi điểm pj ∈ H, trong đó 2 ≤ j ≤ h ta xác định khoảng cách giữa các điểm pj và l1 . Vì tất cả các điểm này là tập đỉnh của bao lồi conv(S) nên khi ta lần lượt xét tới các điểm theo thứ tự ngược chiều kim đồng hồ thì các khoảng cách này sẽ tăng dần tới khi gặp một điểm mà có khoảng cách lớn nhất và sau đó khi xét tiếp đến các đỉnh tiếp theo thì các khoảng cách này lại giảm dần. Gọi pi là điểm có khoảng cách lớn nhất và l2 là đường thẳng đi qua pi sao cho l2 song song với l1 (Nếu có hai điểm giống pi thì l2 đi qua cả hai điểm đó). Rõ ràng là l1 và l2 là các đường thẳng tựa trên cặp điểm đối cực của S (hình 1.12a). (b) Gán θ10 bằng góc nhọn tạo bởi l1 và p1 p2 . Gán θ100 bằng góc nhọn tạo bởi l2 và pi pi+1 . (Nếu có hai điểm pi thì ta chọn điểm pi ở bên trái để xác định θ100 ). Gán θ1 := min{θ10 , θ100 }, d01 := p0 pi và d001 := p1 pi . If (d01 ≥ d001 ) then d1 := d01 và e1 := p0 pi , else d1 := d001 và e1 := p1 pi . Sau đó đánh dấu các điểm p0 , p1 và pi là những điểm đã được xét tới. (Nếu có hai điểm như pi thì ta tính khoảng cách từ p0 và p1 đến mỗi điểm pi đó, giá trị lớn nhất sẽ chọn là d1 , cạnh tương ứng đặt là e1 và đánh dấu các điểm pi đó). (c) If (θ10 ≤ θ100 ) then l1 := p1 p2 và l2 := đường thẳng qua pi+1 và song song với l1 , else l2 := pi pi+1 và l1 := đường thẳng qua p1 và song song với l2 . Không mất tính tổng quát, giả sử l2 là đường thẳng chứa cạnh pi pi+1 của bao lồi conve(S). θ20 , θ200 , d02 và d002 được tính tương tự như ở bước trên (hình 1.12b). Gán d2 := max{d02 , d002 } và e2 là cạnh tương ứng với d2 và ta đánh dấu các đỉnh giống như bước trên. (d) Tiếp tục gán l1 , l2 và thực hiện giống bước (c) tới khi mọi đỉnh của bao lồi được đánh dấu. Khi đó ta có nhiều nhất h khoảng cách d1 , d2 , ..., dh và tương ứng có nhiều nhất h cạnh e1 , e2 , ..., eh . (e) Đường kính của S là max{d1 , d2 , ..., dh } và cạnh tương ứng sẽ cho ta cặp điểm xa nhất của S. 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 2 Các thuật toán tìm bao lồi Trong chương này ta xét các thuật toán tìm bao lồi trong không gian hai chiều như thuật toán gói quà, thuật toán quét Graham, thuật toán Quickhull và thật toán Chan. Trong rất nhiều tài liệu viết về bài toán tìm bao lồi đòi hỏi giả thiết không có ba điểm bất kỳ nào thẳng hàng nhưng điều kiện này là không cần thiết và làm mất tính tổng quát của bài toán. Một số thuật toán cần có điều kiện không thẳng hàng nhưng không phải là ba điểm bất kỳ mà những bộ ba điểm đặc biệt tùy thuộc vào thuật toán cụ thể nào đó. Những điều kiện này có thể vượt qua bằng cách đơn giản và hiệu quả như chúng ta sẽ thấy chương này. Trước khi trình bày các thuật toán này ta đưa ra một số khái niệm và thuật toán cơ bản sau. 2.1 Một số khái niệm và thuật toán cơ bản Đầu tiên ta trình bày định nghĩa sự định hướng của các điểm bất kỳ. Định nghĩa này là cơ sở của những định nghĩa ta sẽ trình bày dưới đây. Định nghĩa 2.1. Cho một bộ ba điểm đã sắp thứ tự (p, q, r) trong mặt phẳng, ta nói rằng chúng có định hướng dương nếu theo thứ tự đã sắp xếp chúng tạo thành hình ngược chiều kim đồng hồ, có định hướng âm nếu chúng tạo thành hình thuận chiều kim đồng hồ và hướng không nếu chúng thẳng hàng (trong đó bao gồm cả trường hợp có hai hay nhiều hơn các điểm trùng nhau) (hình 2.1). Lưu ý rằng sự định hướng phụ thuộc vào thứ tự các điểm được đưa ra. Để xét hướng của các điểm sắp thứ tự (p, q, r) với p = (px , py ), q = (qx , qy ) và r = (rx , ry ) thì ta có thể sử dụng công thức tính định thức cấp ba như dưới đây. Ta định nghĩa ! Orient(p, q, r) := det 1 px py 1 q x qy 1 rx ry . 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (a) Định hướng dương (b) Định hướng âm (c) Hướng không Hình 2.1 Sự định hướng Khi đó bộ ba điểm sắp thứ tự (p, q, r) có định hướng dương nếu Orient(p, q, r) > 0, có định hướng âm nếu Orient(p, q, r) < 0 và có hướng không nếu Orient(p, q, r) = 0. Định hướng của bộ ba điểm, tức là dấu của Orient(p, q, r), là không thay đổi nếu những điểm này bị xoay đi một góc bất kì. Nhận xét 2.1. Ta cũng có thể dùng định thức cấp hai để tính Orient(p, q, r) như sau. Trước tiên ta chọn một trong ba điểm và tính hai vec tơ xuất phát từ điểm đó. Giả sử ta chọn điểm p và tính hai véc tơ → − pq = (qx − px , qy − py ) và → − pr = (rx − px , ry − py ). Khi đó ta có  Orient(p, q, r) = det qx − p x qy − py rx − px ry − py  . 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Xem thêm -