Định lí Helly và ứng dụng

Định lí Helly là một định lí rất quan trong phần hình học tổ hợp. Định lí này cho ta một điều kiện đủ để nhận biết khi nào một họ các hình lồi có giao khác rỗng. Đối với một lớp tập hợp cụ thể như hình bình hành, đoạn thẳng thì có giảm nhẹ điều kiện của định lí Helly. Và ở đây, ta còn xét sự mở rộng của định lý, đặc biệt đối với tập hợp có thể không lồi như cung đường tròn chẳng hạn. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Định lí Helly và ứng dụng Hội thảo khoa học, Hưng Yên 25-26/02/2017 ĐỊNH LÍ HELLY VÀ ỨNG DỤNG Nguyễn Thị Tâm - Hoàng Thị Nhung - Trần Thi Hằng THPT Chuyên Hưng Yên Tóm tắt nội dung Định lí Helly là một định lí rất quan trong phần hình học tổ hợp. Định lí này cho tamột điều kiện đủ để nhận biết khi nào một họ các hình lồi có giao khác rỗng. Đối với mộtlớp tập hợp cụ thể như hình bình hành, đoạn thẳng thì có giảm nhẹ điều kiện của định líHelly. Và ở đây, ta còn xét sự mở rộng của định lý, đặc biệt đối với tập hợp có thể khônglồi như cung đường tròn chẳng hạn.1 Cơ sở lý thuyết1.1 Các định lí HellyĐịnh lý 1 (Định lí Helly trong không gian một chiều). Trên đường thẳng cho n hình lồi(n ≥ 3). Biết rằng giao của hai hình bất kì trong chúng khác rỗng. Khi đó, giao của n hình lồi đãcho khác rỗng.Định lý 2 (Định lí Helly trong không gian hai chiều). Cho trước n hình lồi trên mặt phẳng(n ≥ 4). Biết rằng giao của ba hình lồi bất kì trong chúng khác rỗng. Khi đó, giao của các hình lồiđã cho khác rỗng.Định lý 3 (Định lí Helly trong không gian ba chiều). Cho trước n hình lồi trong không gian(n ≥ 5).Biết rằng giao của bốn hình bất kì trong chúng khác rỗng. Khi đó giao của các hình lồi đãcho khác rỗng.Định lý 4 (Định lí Helly trong không gian n chiều). Cho trước n hình lồi trong không giank - chiều Rk (n ≥ k + 1, k ∈ N ∗ ). Biết rằng (k + 1) hình lồi bất kì trong chúng có giao khác rỗng.Khi đó, giao của các hình lồi đã cho khác rỗng.1.2 Một số hệ quả của định lí HellyHệ quả 1. Cho trước n đoạn thẳng [ ai ; bi ] (i = 1,2,3,. . . ,n) trên cùng một đường thẳng. Khiđó giao của các đoạn thẳng này khác rỗng khi chỉ và chỉ khi giao của hai đoạn thẳng bấtkỳ trong chúng khác rỗng.Chứng minh. Ta chú ý mọi tập lồi A trên đường thẳng thể hiện hoặc là đoạn thẳng, hoặclà một tia hoặc là cả đường thẳng. Định lí Helly với giả thiết trong trường hợp này thựcsự có ý nghĩa khi các tệp A1 , A2 , . . . , An là những đoạn thẳng (còn những trường hợpkhác như trong số những tập hợp này tia và đường thẳng thì ta cũng đưa về trường hợp 205 Hội thảo khoa học, Hưng Yên 25-26/02/2017tất cả là đoạn thẳng).Mỗi đoạn thẳng Ai trên đường thẳng số được xác định bởi hai số tại hai điểm cuối ai , bivà ai ≤ bi . Số ai gọi là đầu trái của Ai , còn bi gọi là đầu phải của Ai . Lấy b là số nhỏ nhấtcủa bi , i = 1, 2, . . . , n; a là số lớn nhất của ai , i = 1, 2, . . . , n. Ta chứng minh rằng a ≤ b.Thật vậy, giả sử a > b. Vì a trùng với một trong những số nào đó trong ai , i = 1, 2, . . . , n,còn b trùng với một trong những số nào đó trong bi , i = 1, 2, . . . , n, thì ai1 = a > b = bi2 .Khi đó chỉ ra rằng những đoạn thẳng Ai1 (với đầu trái ai1 ) và Ai2 (với đầu phải Bi2 ) khôngcó điểm chung. Ta nhận được sự vô lí.Hệ quả 2. Cho trước một họ I các đoạn thẳng [ ai ; bi ] (i ∈ I, I ⊂ N) trên cùng một đườngthẳng. Khi đó giao của các đoạn thẳng này khác rỗng khi và chỉ khi giao của hai đoạnbất kỳ trong chúng khác rỗng. Hình bình hành có các tính chất đặc biệt hơn những hình lồi khác. Đặc biệt hơn lànhững hình bình hành có các cạnh song song với hai đường thẳng cố định. Khi đó, theođịnh lí Helly ta còn có các hệ quả sau:Hệ quả 3. Cho hình bình hành F1 , F2 , F3 , các cạnh của chúng song song với hai đườngthẳng cố định. Khi đó, nếu mọi cặp hai hình trong chúng có điểm chung, thì cả ba hìnhbình hành cũng có điểm chung.Chứng minh. Ta chọn trong mặt phẳng hệ tọa độ với các trục nằm trên hai đường thẳngđã cho (không nhất thiết hệ tọa độ vuông góc, ta đang xét hệ tọa độ bất kì.) Kí hiệu A1 làđiểm chung của F2 và F3 , A2 là điểm chung của F1 và F3 , A3 là điểm chung của của F1 vàF2 . Kí hiệu ( xi , yi ) là tọa độ của điểm Ai đơi với hệ tọa độ đã chọn (i = 1; 2; 3). Không mấttính tổng quát, ta có thể giả thiết những hình bình hành F1 , F2 , F3 được gán nhãn sao chovới các tọa độ tương ứng x1 , x2 , x3 thỏa mãn bất đẳng thức x1 ≤ x2 ≤ x3 . Hình bình hànhF1 sẽ chứa các điểm A2 và A3 (hình 3.7). Khi đó, nó chứa tất cả những điểm P với tọa độ( x, y) sao cho x2 ≤ x ≤ x3 , y2 ≤ y ≤ y3 với y2 ≤ y3 hoặc là y3 ≤ y ≤ y2 với y3 ≤ y2 (hình1 là trường hợp thứ hai).Tương tự, F2 chứa tất cả những điểm P có tọa độ ( x, y) sao cho x1 ≤ x ≤ x3 , y1 ≤ y ≤ y3hoặc là y3 ≤ y ≤ y1 phụ thuộc vào y1 ≤ y3 hoặc là y3 ≤ y1 . Ta lặp lại lí luận trên với hìnhbình hành F3 , ta sẽ thui được sự tồn tại điểm P với tọa độ ( x2 , z), mà nó nằm trên cả bahình bình hành. Thật vậy, cho các chỉ số i; j; k nhận những giá trị 1; 2; 3 và giả sử rằng bấtđẳng thức sau đúng yi ≤ y j ≤ yk . Khi đó bằng cách đặt yi = z, sẽ nhận được kết quả cầnthiết.Từ kết quả trên và định lí Helly suy ra kết quả:Hệ quả 4. Trong ...