Luận văn Thạc sĩ Toán học: Sử dụng kỹ thuật “phễu” tìm đường ngắn nhất giữa hai điểm trong đa giác đơn và trên mặt khối đa diện

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:72

Thêm vào BST

Báo xấu

17
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của luận văn là trình bày hệ thống các kiến thức cơ bản về lý thuyết đồ thị, độ phức tạp thuật toán, định nghĩa đa giác đơn, phép tam giác phân đa giác. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Sử dụng kỹ thuật “phễu” tìm đường ngắn nhất giữa hai điểm trong đa giác đơn và trên mặt khối đa diện

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẶNG THỊ NGỌC ÁNH SỬ DỤNG KỸ THUẬT "PHỄU" TÌM ĐƯỜNG NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN VÀ TRÊN MẶT KHỐI ĐA DIỆN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2016
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - - - - - - - - - o0o - - - - - - - - - ĐẶNG THỊ NGỌC ÁNH SỬ DỤNG KỸ THUẬT "PHỄU" TÌM ĐƯỜNG NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN VÀ TRÊN MẶT KHỐI ĐA DIỆN Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 06 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. PHAN THÀNH AN Hà Nội - 2016
Lời cảm ơn Lời đầu tiên trong bản luận văn này cho phép tôi được gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy Phan Thành An, thầy đã dành nhiều thời gian quý giá của mình tận tình chỉ bảo, hướng dẫn và giúp đỡ để tôi có thể hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô đã dạy bảo tôi trong suốt quá trình học tập, đặc biệt là các thầy cô trong khoa Toán Cơ Tin học, trường Đại Học Khoa Học Tự Nhiên, Đại Học Quốc Gia Hà Nội. Tôi cũng xin được gửi lời cảm ơn tới gia đình, bạn bè và các anh chị trong cùng nhóm nghiên cứu đã luôn cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Đặc biệt, tôi xin gửi lời cảm ơn tới anh Lê Hồng Trang, em Đồng Văn Việt, em Phong Thị Thu Huyền đã giúp đỡ tôi trong quá trình nghiên cứu và hoàn thiện luận văn, cùng với chị Nguyễn Thị Vân Hòa, anh Phạm Quang Khoái và các anh chị em trong bộ môn Toán trường Đại học Lâm nghiệp đã tạo điều kiện rất nhiều để tôi có thêm thời gian học tập và nghiên cứu luận văn. Hà Nội, tháng 10 năm 2016 Học viên Đặng Thị Ngọc Ánh 1
Mục lục 1 Kiến thức chuẩn bị 5 1.1 Một số kiến thức cơ bản về lý thuyết đồ thị và độ phức tạp thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Đồ thị, cây và chu trình . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Độ phức tạp thuật toán . . . . . . . . . . . . . . . . . . . . 7 1.2 Định nghĩa đa giác đơn và đường gấp khúc . . . . . . . . . . . . . 8 1.3 Phép tam giác phân đa giác . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Khái niệm điểm trong và điểm trong tương đối . . . . . . . . . . . 12 1.5 Định nghĩa dãy mặt tam giác và đường đi dọc theo dãy mặt tam giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Khái niệm góc tại một điểm trên bề mặt khối đa diện . . . . . . . 15 1.7 Phép lật . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Thuật toán tìm đường đi ngắn nhất giữa 2 điểm trong đa giác đơn sử dụng kỹ thuật “phễu” của Lee và Preparata 19 2.1 Cây đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Hình ống tay và hình phễu . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Thuật toán tìm đường đi ngắn nhất giữa 2 điểm trong hình ống tay 24 2.4 Chứng minh tính đúng và đánh giá độ phức tạp của thuật toán . 26 2.4.1 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . 26 2.4.2 Đánh giá độ phức tạp của thuật toán . . . . . . . . . . . . 28 2.5 Chương trình minh họa thuật toán trên java . . . . . . . . . . . . 29 3 Thuật toán tìm đường đi ngắn nhất giữa hai điểm trên bề mặt 2
khối đa diện 34 3.1 Hình phễu trong không gian 3 chiều . . . . . . . . . . . . . . . . . 35 3.2 Thuật toán tìm đường đi ngắn nhất giữa hai điểm dọc theo dãy mặt tam giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Chứng minh tính đúng đắn và đánh giá độ phức tạp của thuật toán 42 3.3.1 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . 42 3.3.2 Đánh giá độ phức tạp của thuật toán . . . . . . . . . . . . 46 3.4 Ví dụ minh họa cho thuật toán trên phần mềm javaview . . . . . 46 Kết luận 56 Tài liệu tham khảo 58
Danh mục ký hiệu [a, b] hoặc ab Đoạn thẳng nối 2 điểm a và b a1 a2 ...ak Đường gấp khúc đi qua các đỉnh a1 , a2 , ..., ak S = {f1 , f2 , ..., fm+1 } Dãy m + 1 mặt tam giác E = {e1 , e2 , ..., em } Tập m cạnh kề của dãy m + 1 mặt tam giác fi ∩ fi+1 Giao của hai mặt tam giác fi và fi+1 σ Phân hoạch của đoạn [a, b] d(x, y) Khoảng cách Euclid giữa hai điểm x, y dọc theo S length(x, y) Độ dài đoạn thẳng nối 2 điểm x và y SP (x, y) Đường đi ngắn nhất từ x đến y L(x, y) Đường đi tùy ý từ điểm x đến y 4xyz Tam giác có 3 đỉnh lần lượt là x, y, z r(x) hoặc x Ảnh của điểm x qua phép lật r 2
Lời mở đầu Hình học tính toán được bắt nguồn từ lĩnh vực phân tích và thiết kế giải thuật sau những năm 1970, có tầm quan trọng rất thiết thực. Nhiều ứng dụng có thể áp dụng hình học tính toán như nhận dạng mẫu, đồ họa máy tính, xử lý ảnh, tự động hóa, hệ thống thông tin địa lý hay các bài toán trong công nghiệp như cách bố trí mạch kim loại, bản mạch... Giải quyết tốt các bài toán này trên máy tính với tốc độ cao và chính xác là hết sức cần thiết. Trong đó bài toán tìm đường đi ngắn nhất giữa hai điểm trong một miền hình học là một trong những vấn đề cơ bản và có nhiều ứng dụng trong kỹ thuật robot, kỹ thuật tự động, thông tin địa lý. . . (xem [5],[18]). Thực tế đó đã thu hút rất nhiều nhà toán học quan tâm nghiên cứu như Dijkstra, Lee, Preparata, O’Rourke . . . Luận văn tập trung nghiên cứu thuật toán tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn trong không gian 2 chiều, sau đó phát triển thuật toán tìm đường đi ngắn nhất giữa 2 điểm trên bề mặt khối đa diện trong 3 chiều. Với bài toán tìm đường đi ngắn nhất trong đa giác đơn, năm 1984 các tác giả Lee và Preparata đã đưa ra thuật toán để giải quyết bài toán với độ phức tạp về thời gian là tuyến tính, thông qua việc tam giác phân đa giác, sau đó thuật toán tiếp tục xây dựng các hình “phễu” sao cho đường biên của phễu chứa đường đi ngắn nhất cần tìm (xem [13]). Dựa trên ý tưởng đã được trình bày trong bản thảo của An, Giang, Phú và Polthier (xem [7]), luận văn tiếp tục trình bày chi tiết thuật toán sử dụng kỹ thuật “phễu” tương tự trong 2 chiều kết hợp với kỹ thuật lật để tìm đường đi ngắn nhất giữa hai điểm trên bề mặt khối đa diện trong không gian 3 chiều. 3
Từ đó tác giả chọn đề tài “Sử dụng kỹ thuật “phễu” tìm đường ngắn nhất giữa hai điểm trong đa giác đơn và trên mặt khối đa diện”. Luận văn được chia thành ba chương. Chương 1: Kiến thức chuẩn bị. Với quan điểm là chương cơ sở, trong phần này chúng tôi trình bày hệ thống các kiến thức cơ bản về lý thuyết đồ thị, độ phức tạp thuật toán, định nghĩa đa giác đơn, phép tam giác phân đa giác. Ngoài ra, trong phần này chúng tôi cũng trình bày thêm các kiến thức về dãy mặt tam giác, đường đi dọc theo dãy mặt, định nghĩa phép lật và các tính chất của phép lật trong không gian 3 chiều. Đây là những kiến thức cơ sở cần thiết cho chương 2 và chương 3. Chương 2: Thuật toán tìm đường đi ngắn nhất giữa 2 điểm trong đa giác đơn sử dụng kỹ thuật “phễu” của Lee và Preparata. Chương này trình bày chi tiết thuật toán sử dụng kỹ thuật phễu của Lee và Preparata trong bài báo đăng trên tạp chí Networks năm 1984 (xem [13]). Sau đó chúng tôi trình bày ví dụ cụ thể minh họa cho từng bước của thuật toán bằng các hình ảnh minh họa từ chương trình được viết bằng ngôn ngữ lập trình java bởi Josh Tyler năm 1998. Chương 3: Thuật toán tìm đường đi ngắn nhất giữa hai điểm trên bề mặt khối đa diện. Chương cuối trình bày định nghĩa phễu trong không gian 3 chiều được đưa ra bởi An, Giang, Phú và Polthier (xem [7]) và chứng minh một số tính chất mới của phễu. Sau đó dựa trên ý tưởng của thuật toán đã trình bày trong [7], chúng tôi trình bày thuật toán mới tiếp tục sử dụng kỹ thuật phễu để tìm đường đi ngắn nhất giữa hai điểm trên bề mặt của một khối đa diện trong không gian 3 chiều. Phần cuối chương là một số ví dụ cụ thể minh họa cho thuật toán trên phần mềm hình học tính toán javaview. Hà Nội, ngày 11 tháng 10 năm 2016 Học viên Đặng Thị Ngọc Ánh 4
Chương 1 Kiến thức chuẩn bị Trong chương này luận văn tập trung trình bày một số kiến thức làm cơ sở cho việc trình bày và nghiên cứu nội dung của các chương tiếp theo. 1.1 Một số kiến thức cơ bản về lý thuyết đồ thị và độ phức tạp thuật toán 1.1.1 Đồ thị, cây và chu trình Lý thuyết đồ thị là một trong những ngành khoa học ra đời khá sớm và gắn kết nhiều ngành khoa học với nhau, giúp chúng ta mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như đường đi, chu trình, đường đi ngắn nhất... Các khái niệm sau được trình bày theo tài liệu [3]. Định nghĩa 1.1.1. Tập hợp V 6= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của V được gọi là một đồ thị. Kí hiệu là G = (V, E). • V là tập hợp các đỉnh. • E ⊆ V × V là tập hợp các cạnh. Nếu cặp đỉnh không sắp thứ tự được gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng. Ví dụ 1.1.1. Cho đồ thị G như trong hình dưới đây. 5
b a c e d Hình 1.1: Đồ thị hữu hạn có 5 đỉnh - Tập đỉnh V = {a, b, c, d, e} - Tập cạnh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)} Nếu (a, b) là một cạnh của đồ thị G thì ta nói đỉnh b kề với đỉnh a, hay hai đỉnh a và b cùng kề với cạnh (a, b). Hai cạnh kề nhau là hai cạnh có ít nhất một đỉnh chung. Đồ thị vô hướng là đồ thị chỉ chứa các cạnh vô hướng. Đơn đồ thị (gọi tắt là đồ thị) là đồ thị mà mỗi cặp đỉnh được nối với nhau bởi không quá một cạnh. Định nghĩa 1.1.2. Cho đồ thị G = (V, E), đường đi trong đồ thị là một dãy các đỉnh < x1 , x2 , ..., xk > sao cho mỗi đỉnh trong dãy(không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là ∀i = 2, 3, ..., k cạnh (xi−1 , xi ) ∈ E . Ta nói đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk . Định nghĩa 1.1.3. Chu trình là một đường đi khép kín (đỉnh cuối trùng với đỉnh đầu của đường đi). Chu trình đơn là chu trình mà các đỉnh trên nó khác nhau từng đôi một. Trong đồ thị G = (V, E), bậc của đỉnh v trong đồ thị, kí hiệu là deg(v) là số cạnh kề với đỉnh v . Tiếp theo, chúng tôi trình bày một khái niệm cơ bản trong lý thuyết đồ thị. Đó là khái niệm cây được Caley đưa ra đầu tiên vào năm 1857. Cây là đồ thị vô hướng liên thông không có chu trình. 6
1.1.2 Độ phức tạp thuật toán Một công việc có thể có nhiều cách khác nhau để thực hiện, nhất là thuật toán. Có thể có nhiều thuật toán khác nhau thực hiện một công việc. Ta phải tìm một ngôn ngữ nào đó để so sánh được tốc độ thực hiện thuật toán khi làm cùng một việc. Một thước đo hiệu quả của thuật toán là đo thời gian mà 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. Gắn với thời gian gian tính toán là độ phức tạp thời gian. Việc biết được độ phức tạp thời gian cho một thuật toán là rất quan trọng, vì ta có thể kiểm soát được thời gian chạy thuật toán là một phút, một năm hay một triệu năm. Một thước đo thứ hai là đo 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 với bộ nhớ tính toán là độ phức tạp không gian. Việc biết độ phức tạp về không gian cho ta bước chuẩn bị và thấy được khả năng đáp ứng trong việc thực thi thuật toán. Độ phức tạp về không gian gắn với cấu trúc dữ liệu nên trong phạm vi luận văn, chúng tôi bỏ qua độ phức tạp về không gian. Độ phức tạp về thời gian của thuật toán có thể được xem xét qua các phép toán được dùng. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc cỡ đầu vào n của thuật toán. Tùy thuộc từng bài toán mà n có thể nhận những giá trị khác nhau. Ví dụ bài toán tính giai thừa thì n là số cần tính giai thừa, nhưng trong phép tính đối với ma trận thì n lại là số hàng hoặc số cột của ma trận. Tuy nhiên, phần lớn số các phép toán cơ bản thực hiện thuật toán là hoàn toàn khác nhau với cùng một cỡ đầu vào. Do đó người ta đưa ra các khái niệm sau (xem [1]). • Độ phức tạp trường hợp tốt nhất • Độ phức tạp trường hợp xấu nhất 7
• Độ phức tạp trường hợp trung bình Tuy nhiên, trong ứng dụng thực tiễn chúng ta không cần biết chính xác hàm tính toán này mà chỉ cần biết một ước lượng đủ tốt của chúng. Để ước lượng độ phức tạp thuật toán, ta thường dùng khái niệm bậc Ô-lớn. Định nghĩa 1.1.4. (xem [1]) Cho một hàm số g(n) xác định dương, ta định nghĩa O(g(n)) là tập hợp tất cả các hàm f (n) xác định dương và thỏa mãn: ∃ hằng số c và n0 sao cho ∀n > n0 và f (n) 6 cg(n). Khi đó nếu f (n) ∈ O(g(n)) thì ta nói rằng f (n) là Ô lớn của g(n). Một số tính chất về độ phức tạp của thuật toán 1. Nếu f1 (n) ∈ O(g1 (n)) và f2 (n) ∈ O(g2 (n)) thì f1 (n) + f2 (n) ∈ O(g1 (n) + g2 (n)). 2. Nếu f1 (n) ∈ O(g1 (n)) và f2 (n) ∈ O(g2 (n)) thì f1 (n).f2 (n) ∈ O(g1 (n).g2 (n)). 3. Cho P (n) = ak nk + ak−1 nk−1 + ... + a1 n + a0 là đa thức bậc k, ak > 0. Khi đó P (n) ∈ O(nk ). Một số độ phức tạp thường gặp • Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. • Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. • Độ phức tạp đa thức, O(P (n)) với P là đa thức bậc cao (từ bậc 2 trở lên). • Ngoài ra còn có các độ phức tạp logarit O(logn) hoặc hàm mũ O(2n ). Trường hợp hàm mũ là trường hợp xấu nhất và khó thực hiện trên thực tế. 1.2 Định nghĩa đa giác đơn và đường gấp khúc Để có thể định nghĩa chính xác về đa giác đơn, ta cần phải sử dụng kết quả của định lý đường cong Jordan. Định lý đường cong Jordan đã chỉ ra rằng bất 8
bỳ một đường cong đơn khép kín nào cũng chia mặt phẳng thành 2 phần, trong đó có một phần bị giới hạn bởi phần còn lại (xem [12] hoặc [15]). Để có thể định nghĩa về đường cong đơn khép kín là một vấn đề không dễ. Theo lý thuyết topo đường cong đơn khép kín J (xem [12]) còn gọi là đường cong Jordan, là ảnh của một ánh xạ liên tục 1-1 từ R/Z vào R2 . Hai phần được xác định bởi một đường cong Jordan được gọi là phần trong và phần ngoài của đường cong. Trong đó, miền bị chặn được gọi là phần trong và miền không bị chặn được gọi là phần ngoài (xem thêm [15]). Đây cũng là cơ sở để có thể xây dựng định nghĩa về đa giác đơn. Trước hết, ta cần nhắc lại một số khái niệm cơ bản có liên quan (xem [16]). q Không gian Rn (∀n > 1) được trang bị chuẩn kxk = x21 + x22 + ... + x2n với x = (x1 , x2 , ..., xn ) ∈ Rn được gọi là không gian Euclid n chiều, kí hiệu E = Rn . Kí hiệu d(x, y) là khoảng cách Euclid giữa hai điểm x, y trong E . Đường đi trong R2 là một ánh xạ liên tục γ : [a, b] ⊂ R → R2 Nếu γ(a) = x và γ(b) = y thì x, y là các điểm cuối của γ và ta nói rằng đường γ nối các điểm x và y . Một phân hoạch của đoạn [a, b], kí hiệu là σ được xác định bởi một dãy hữu hạn các số thực ti , i = 0, ..., n thỏa mãn a = t0 6 t1 < ... < tn−1 6 tn = b với n > 1. Định nghĩa 1.2.1. Độ dài của đường γ : [a, b] → Rn kí hiệu là length(γ) được xác định như sau: n−1 X length(γ) := sup d(γ(ti ), γ(ti+1 )) σ i=0 Đoạn thẳng đi qua hai điểm a và b, kí hiệu là [a, b] hoặc ab (xem [15]) là một tập con đóng của đường thẳng đi qua hai điểm a và b, các điểm này được gọi là các điểm cuối của đoạn thẳng [a, b]. Tập con đóng ở đây bao gồm cả các điểm cuối. 9
Theo [15] đa giác đơn là miền phẳng được giới hạn bởi một tập hữu hạn các đoạn thẳng tạo thành một đường cong đơn khép kín. Tuy nhiên, để tránh đưa lý thuyết topo vào bài viết chúng ta trình bày định nghĩa đa giác đơn như sau. Định nghĩa 1.2.2. (xem [15]) Cho v0 , v1 , v2 , ..., vn−1 là n điểm thuộc cùng một mặt phẳng, kí hiệu ei = [vi , vi+1 ] với 0 6 i 6 n − 1 và vn ≡ v0 là n đoạn thẳng nối các điểm đã cho. Khi đó miền trong được giới hạn bởi những đoạn thẳng này được gọi là một đa giác đơn nếu và chỉ nếu chúng thỏa mãn các điều kiện sau: 1. Mỗi đoạn thẳng kề nhau ei và ei+1 có duy nhất một điểm chung là vi+1 . Tức là ei ∩ ei+1 = vi+1 với i = 0, ..., n − 1. 2. Các đoạn thẳng không kề nhau thì không cắt nhau. Tức là ei ∩ ej = ∅ với j 6= i + 1. Điểm vi được gọi là đỉnh của đa giác đơn và đoạn ei gọi là cạnh của đa giác đơn. Kí hiệu đa giác đơn với các đỉnh vi là P = (v0 , v1 , ..., vn−1 ). Hình 1.2: Đa giác không đơn Hình 1.3: Đa giác đơn Đường gấp khúc q1 q2 ...qk là một dãy có thứ tự các điểm qi (i = 1, 2, ..., k ) sao cho mỗi cặp điểm kề nhau qi và qi+1 (i = 1, 2, ..., k − 1) thể hiện một đoạn thẳng. Các điểm qi gọi là các đỉnh của đường gấp khúc (xem [13]). Một đường gấp khúc gọi là đơn nếu bất kỳ hai đoạn thẳng không liên tiếp trong đó đều không cắt nhau. 10
q8 q3 q4 q6 q1 q7 q1 q8 q5 q4 q3 q6 q7 q2 q5 q2 Hình 1.4: Đường gấp khúc có 8 Hình 1.5: Đường gấp khúc đơn có đỉnh 8 đỉnh Tiếp theo, chúng tôi trình bày định nghĩa về tiếp tuyến và đường cong lồi theo [20] như sau. Một đường thẳng l đi qua một điểm A của đường cong γ được gọi là một tiếp tuyến với γ tại A nếu đường cong đó nằm hoàn toàn trong nửa mặt phẳng được xác định bởi l (xem [20] trang 15). Đường cong γ được gọi là đường cong lồi nếu mỗi điểm trên đó đều tồn tại duy nhất một đường tiếp tuyến (xem [20] trang 15). 1.3 Phép tam giác phân đa giác Đường chéo của đa giác đơn P là đoạn thẳng [vi , vj ] nằm trong đa giác và thỏa mãn điều kiện không cắt bất kỳ cạnh nào của P , với j 6= i + 1 và 0 6 i, j 6 n − 1 (xem [13]). Hai đường chéo gọi là không cắt nhau nếu tập hợp các giao điểm của chúng nằm trong tập hợp các điểm cuối của chúng. Phép tam giác phân đa giác là phép phân chia một đa giác P thành các tam giác bởi các đường chéo không cắt nhau của P . Với một đa giác tùy ý luôn tồn tại ít nhất một cách tam giác phân đa giác (xem [15], trang 7). Có nhiều thuật toán tam giác phân khác nhau đã được nghiên cứu với độ phức tạp về thời gian là O(nlog n) (xem [15], [10]) hoặc độ phức tạp là O(n) (xem [6], [24]). 11
Sau đây là một số kết quả đã được chứng minh trong [15]: 1. Mỗi đa giác có số đỉnh lớn hơn hoặc bằng 4 đều tồn tại ít nhất một đường chéo (Bổ đề 1.2.2). 2. Mỗi đa giác P có n đỉnh đều có thể phân chia thành các tam giác bằng cách thêm vào (tối thiểu là 0) các đường chéo (Định lý 1.2.3). 3. Mỗi phép tam giác phân một đa giác P có n đỉnh sử dụng n − 3 đường chéo và chia P thành n − 2 tam giác (Bổ đề 1.2.4). d7 d1 d6 d3 d8 d2 d4 d5 Hình 1.6: Một phép tam giác phân đa giác có 11 đỉnh thành 9 tam giác bởi 8 đường chéo 1.4 Khái niệm điểm trong và điểm trong tương đối Cho một tập C ⊂ Rn , bao đóng của C kí hiệu C là giao của tất cả các tập đóng chứa C (xem [4]). Một điểm x ∈ C gọi là một điểm trong của C nếu có một hình cầu tâm x nằm trọn trong C . Tập các điểm trong của C gọi là phần trong của C và ký hiệu là intC . Tập C ⊂ Rn gọi là một tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Nói cách khác, (1 − λ)a + λb ∈ C với mọi a, b ∈ C và 0 6 λ 6 1. Một điểm x thuộc tập lồi C ⊂ Rn gọi là một điểm trong tương đối của C nếu với mỗi a ∈ C đều có một số λ > 0 để điểm x + λ(a − x) ∈ C . Tập các điểm trong tương đối của C gọi là phần trong tương đối của C kí hiệu là riC . Tập hợp C \ riC gọi là biên tương đối của C kí hiệu là ∂C . Một điểm thuộc ∂C gọi là điểm biên của tập lồi C . 12
x ∈ intC x ∈ ∂C C Hình 1.7: Minh họa điểm trong và điểm biên của tập C 1.5 Định nghĩa dãy mặt tam giác và đường đi dọc theo dãy mặt tam giác Trước hết, ta trình bày một số khái niệm cơ bản sau. Khối đa diện trong không gian R3 được xác định bởi một tập hữu hạn các đa giác sao cho mỗi cạnh của đa giác này trùng với đúng một cạnh của đa giác khác (tức là các đa giác kề nhau). Khi đó các đỉnh và các cạnh của đa giác cũng là các đỉnh và cạnh của khối đa diện (xem [21]). Bề mặt của khối đa diện bao gồm tất cả các đỉnh, các cạnh và miền trong của các đa giác. Trong luận văn này chúng tôi giả thiết rằng bề mặt của khối đa diện bao gồm các mặt tam giác. Hình 1.8: Minh họa một khối đa diện có 98 mặt tam giác (Tham khảo [7]) Cho S = {f1 , f2 , ..., fm+1 } là một dãy mặt tam giác nằm trên bề mặt của khối đa diện P , cho x và y là hai điểm thỏa mãn điều kiện: (A1 ) x ∈ f1 , y ∈ fm+1 và fi ∩ fi+1 là một cạnh của P với (i = 1, ..., m). 13
Từ sau phần này, khi cho x, y ∈ S có nghĩa là x, y thỏa mãn điều kiện (A1 ) và fi ∩ fi+1 := ei . Định nghĩa 1.5.1. (xem [7]) Đường đi dọc theo dãy mặt S = {f1 , f2 , ..., fm+1 } nối hai điểm x và y là một ánh xạ liên tục γ : [a, b] ⊂ R → S thỏa mãn điều kiện: • γ(a) = x; γ(b) = y • γ([a, b]) ⊂ ∪m+1 i=1 fi • Tồn tại một phân hoạch σ của đoạn [a, b], sao cho a 6 t1 < ... < tm 6 b và γ(ti ) ∈ ei với (i = 1, ..., m). Tiếp theo ta làm rõ định nghĩa độ dài đường đi dọc theo dãy mặt tam giác S như sau. Định nghĩa 1.5.2. (xem [7]) Cho γ là một đường đi từ điểm x tới điểm y dọc theo dãy mặt S , khi đó n−1 X length(x, y) := length(γ) := sup d(γ(ti ), γ(ti+1 )) σ i=0 được gọi là độ dài đường γ . Ở đây supremum được lấy theo tập hợp các phân hoạch σ = {ti }ni=0 của [a, b]. Một đường đi được gọi là đo được nếu độ dài của nó là hữu hạn. Bổ đề 1.5.1. (xem [7]) Cho x và y là hai điểm thuộc dãy mặt S , khi đó luôn tồn tại một đường đi đo được nối x và y dọc theo S . Gọi Γ là tập hợp tất cả các đường γ : [a, b] → S nối điểm x và y . Định nghĩa 1.5.3. Đường đi γ ∗ nối x và y dọc theo S gọi là một đường đi ngắn nhất nếu thỏa mãn: length(γ ∗ ) = inf {γ} γ∈Γ 14
1.6 Khái niệm góc tại một điểm trên bề mặt khối đa diện Trong phần này, ta nhắc lại các khái niệm về tổng các góc tại một đỉnh, và góc bên trái, bên phải tại một điểm của đường đi trên bề mặt khối đa diện (xem [17]). Cho v là một đỉnh của S và {f1 , f2 , ..., fk } ⊂ S là một tập các mặt tam giác có chung đỉnh v và θi lần lượt là các góc nằm trong tam giác fi tại v (1 6 i 6 k ). Pk Khi đó, tổng các góc tại đỉnh v là góc θ được xác định bởi θ = i=1 θi . v p0 γ3 p γ1 γ2 Hình 1.9: Góc tại một điểm trên 3 đường đi γ1 , γ2 và γ3 Xét đường đi γ trên bề mặt khối đa diện, góc trái và góc phải của đường γ tại một điểm lần lượt kí hiệu là θl và θr . Khi đó θl + θr = θ. Nếu γ đi qua một đỉnh v khi đi từ mặt fi đến mặt fj (1 6 i < j 6 k ), giả thiết v ∈ fi ∩ fj thì một trong hai góc θl hoặc θr nằm trên bề mặt của S và góc đó được gọi là góc trong của đường γ tại đỉnh v . Nếu đường γ đi qua một điểm trong tương đối p của cạnh ei ∈ E , khi đó cả θl và θr đều gọi là góc trong của đường γ tại điểm p. Ví dụ trong hình 1.9 - Tại đỉnh v thuộc cả 3 mặt tam giác f4 , f5 , f6 và đường γ3 đi qua v . Khi đó, góc θr là góc trong vì góc này nằm trên bề mặt của S . - Tại điểm p (hoặc p0 ) thuộc đường γ1 (hoặc γ2 ) có 2 góc θl và θr đều là góc trong. 15
1.7 Phép lật Hai mặt tam giác f và f 0 được gọi là kề nhau nếu chúng có chung một cạnh và cạnh chung này được gọi là cạnh kề của 2 mặt tam giác đó. f4 f2 f1 f3 Hình 1.10: Mặt f1 không kề với f4 Hình 1.11: Mặt f1 kề với f2 Dãy các mặt tam giác kề nhau là một dãy các mặt F = {f1 , f2 , ..., fk+1 } với k ≥ 1 sao cho mặt fi kề với fi+1 , i = 1, 2..., k . Định nghĩa phép lật ở đây được trình bày theo [14] trang 649. Trước hết chúng tôi trình bày định nghĩa phép lật tam giác f 0 lên tam giác f quanh cạnh kề e như sau. Phép lật mặt f 0 lên mặt f là xác định ảnh của f 0 lên mặt phẳng chứa mặt f qua phép quay f 0 quanh cạnh kề e sao cho mặt f 0 nằm ở phía đối diện với f (tức là mặt f và f 0 nằm ở hai phía đối với cạnh e). Gọi (α) là mặt phẳng chứa mặt f . Khi đó, định nghĩa phép lật ở trên tương đương với định nghĩa phép lật là ánh xạ r được cho như sau: r : f 0 ⊂ R2 → (α) ⊂ R2 ! ! ! x1 cos θ − sin θ x1 x= 7→ r(x) = . x2 sin θ cos θ x2 Trong đó θ = π − arccos(~a1 , ~a2 ) với 0 6 θ 6 π và ~a1 , ~a2 lần lượt là các véc tơ pháp tuyến của các mặt phẳng chứa f và f 0 . Từ đó phép lật cho một dãy các mặt tam giác được định nghĩa như sau. Định nghĩa 1.7.1. (xem [14]) Cho dãy các mặt tam giác S = {f1 , f2 , ..., fm+1 } với E = {e1 , e2 , ..., em } là dãy các cạnh kề có thứ tự. Phép lật dãy mặt tam giác 16