Bao lồi

màu xanh và màu đỏ.]]
Trong hình học, bao lồi của một hình là tập hợp lồi nhỏ nhất chứa hình đó. Bao lồi có thể được định nghĩa là giao của tất cả tập lồi chứa một tập con cho trước của một không gian Euclid, hoặc là tập hợp gồm tất cả tổ hợp lồi của các điểm trong tập con đó. Đối với một tập con bị chặn của mặt phẳng, bao lồi có thể được minh họa thành một hình bao bởi một dây đàn hồi kéo giãn xung quanh tập con đó.

Bao lồi của tập mở là bao lồi mở, và bao lồi của tập compact là bao lồi compact. Mỗi tập lồi compact đều là bao lồi của các điểm cực biên của nó. Toán tử bao lồi là một ví dụ về toán tử đóng, và một antimatroid có thể được biểu diễn bằng cách áp dụng toán tử đóng này cho tập hợp hữu hạn các điểm. Các bài toán thuật toán về việc tìm bao lồi của một tập hợp hữu hạn các điểm trong mặt phẳng hoặc các không gian Euclid ít chiều khác và bài toán đối ngẫu về các nửa không gian giao nhau đều là những vấn đề cơ bản của hình học tính toán. Chúng có thể được giải trong thời gian O(n\log n) đối với tập hợp điểm hai chiều hoặc ba chiều, và trong thời gian bằng với độ phức tạp thời gian trong trường hợp tệ nhất được cho bởi định lý cận trên ở không gian nhiều chiều hơn.

Cùng với tập hợp điểm hữu hạn, bao lồi cũng đã được nghiên cứu đối với đa giác đơn, chuyển động Brown, đường cong ghềnh và trên đồ thị của hàm. Bao lồi được ứng dụng rộng rãi trong toán học, thống kê, tối ưu hóa tổ hợp, kinh tế, mô hình hóa hình học và tập tính học. Một số cấu trúc liên quan đến nó bao gồm bao lồi trực giao, lớp lồi, chỏm lồi, tam giác đạc Delaunay và sơ đồ Voronoi.

Định nghĩa

Một tập hợp các điểm trên một không gian Euclid được gọi là tập lồi nếu nó chứa các đoạn thẳng nối từng cặp điểm của nó. Bao lồi của một tập X cho trước có thể được định nghĩa là

Tập lồi nhỏ nhất chứa X
Giao của tất cả các tập lồi chứa X
Tập hợp tất cả tổ hợp lồi của các điểm trong X
Hợp của tất cả đơn hình với các đỉnh thuộc X.

Với tập bị chặn trong mặt phẳng Euclid mà các điểm trong tập đó không tạo thành đường thẳng thì đường biên của bao lồi là đường cong Jordan với chu vi nhỏ nhất chứa X. Có thể tưởng tượng rằng ta kéo giãn một dây đàn hồi để nó bao quanh toàn bộ tập S rồi thả dây ra để nó co lại đến mức tối đa; khi đó, dây bao lại tập lồi của S. Cách hiểu này không thể mở rộng được ngay cho không gian nhiều chiều hơn: với một tập hợp hữu hạn các điểm trong không gian ba chiều, một lân cận của một cây bao trùm của các điểm này bao lại chúng với diện tích bề mặt nhỏ tùy ý và nhỏ hơn diện tích bề mặt của bao lồi. Tuy nhiên, trong không gian nhiều chiều, một số dạng của bài toán vật cản về việc tìm một bề mặt năng lượng thấp nhất nằm trên một hình cho trước có thể có bao lồi là nghiệm của chúng.

Với các đối tượng trong không gian ba chiều, định nghĩa đầu tiên phát biểu rằng bao lồi là vùng giới hạn lồi nhỏ nhất của các đối tượng đó. Định nghĩa qua giao của các tập lồi có thể được mở rộng cho hình học phi Euclid, và định nghĩa qua tổ hợp lồi có thể được mở rộng từ không gian Euclid sang không gian vectơ thực hoặc không gian afin bất kỳ; bao lồi cũng có thể được khái quát hóa theo một cách trừu tượng hơn sang matroid định hướng.

Quan hệ giữa các định nghĩa

Định nghĩa đầu tiên không hiển nhiên đúng: vì sao phải tồn tại một tập lồi nhỏ nhất chứa X với mọi X? Tuy nhiên, định nghĩa thứ hai (giao của tất cả các tập lồi chứa X) lại mang tính rạch ròi hơn. Theo đó, bao lồi là tập con của mỗi tập lồi Y khác X chứa X, vì Y có trong các tập được giao. Do đó, nó chính là tập lồi nhỏ nhất chứa X. Vì vậy, hai định nghĩa đầu tiên là tương đương nhau.

Mỗi tập lồi chứa X phải chứa tất cả tổ hợp lồi của các điểm trong X (theo giả thiết rằng nó là tập lồi), nên tập hợp tất cả các tổ hợp lồi này có trong giao của tất cả các tập lồi chứa X. Ngược lại, tập hợp tất cả các tổ hợp lồi cũng là một tập lồi chứa X nên nó cũng chứa giao của tất cả các tập lồi chứa X, và do đó định nghĩa thứ hai và thứ ba là hai định nghĩa tương đương.

Thực tế, theo định lý Carathéodory, nếu X là tập con của một không gian Euclid d chiều, mỗi tổ hợp lồi của một số hữu hạn các điểm trong X cũng là một tổ hợp lồi của nhiều nhất d + 1 điểm trong X. Tập hợp các tổ hợp lồi của một bộ gồm d + 1 điểm là một đơn hình; trong mặt phẳng nó là một tam giác và trong không gian ba chiều nó là một tứ diện. Vì vậy, mỗi tổ hợp lồi của các điểm trong X đều thuộc một đơn hình có các đỉnh thuộc X, nên định nghĩa thứ ba và thứ tư là hai định nghĩa tương đương.

Tính chất tôpô

Bao đóng và bao mở
Bao lồi đóng của một tập hợp là tập đóng của bao lồi, và bao lồi mở là phần trong (hoặc, trong một số tài liệu, phần trong tương đối) của bao lồi.

Bao lồi đóng của X là giao của tất cả các nửa không gian đóng chứa X. Nếu bao lồi của X đã là một tập đóng (xảy ra chẳng hạn khi X là một tập hữu hạn hoặc, tổng quát hơn, là một tập compact) thì nó bằng bao lồi đóng đó. Tuy nhiên, giao của các nửa không gian đóng là tập đóng, nên khi một bao lồi không phải là bao lồi đóng thì nó không thể biểu diễn được theo cách này.

Nếu bao lồi mở của một tập hợp X là bao lồi d chiều thì mỗi điểm trong bao đó thuộc một bao lồi mở gồm nhiều nhất 2d điểm thuộc tập X. Tập hợp các đỉnh của một hình vuông, khối bát diện đều, hoặc khối đa diện chéo trong không gian nhiều chiều là những ví dụ về trường hợp cần đúng 2d điểm.

Sự bảo toàn tính chất tôpô

Về mặt tôpô, bao lồi của một tập mở luôn luôn là bao lồi mở, và bao lồi của một tập compact luôn luôn là bao lồi compact. Tuy nhiên, có một số tập đóng có bao lồi không phải là bao lồi đóng. Chẳng hạn, tập đóng

:\left \{ (x, y)\mathop{\bigg|}y \geq \frac{1}{1 + x^2} \right \}
(tập hợp các điểm thuộc hoặc nằm phía trên đường cong phù thủy Agnesi) có bao lồi là nửa mặt phẳng trên mở.

Tính compact của bao lồi của tập compact trong không gian Euclid với số chiều hữu hạn được khái quát hóa bằng định lý Krein–Smulian, theo đó bao lồi đóng của một tập con compact yếu trong một không gian Banach (một tập con có tính compact dưới dạng tôpô yếu) là bao lồi compact yếu.

Điểm cực biên

Một điểm cực biên của một tập lồi là một điểm trong tập hợp không nằm trên một đoạn thẳng giữa hai điểm khác trong cùng tập hợp đó. Đối với một bao lồi, mỗi điểm cực biên đều phải thuộc tập đã cho, vì ngược lại nó không thể tạo thành một tổ hợp lồi gồm các điểm đã cho. Theo định lý Krein–Milman, mỗi tập lồi compact trong một không gian Euclid (hoặc, tổng quát hơn, trong một không gian vectơ tôpô lồi địa phương) là bao lồi của các điểm cực biên của nó. Tuy nhiên, định lý này có thể không đúng đối với các tập lồi không compact; ví dụ, toàn bộ mặt phẳng Euclid và quả cầu đơn vị mở đều có tính lồi, nhưng chúng không có điểm cực biên nào. Lý thuyết Choquet mở rộng định lý này từ tổ hợp lồi hữu hạn của các điểm cực biên sang tổ hợp vô hạn trong các không gian tổng quát hơn.

Tính chất hình học và đại số

Toán tử đóng
Toán tử bao lồi có các tính chất đặc trưng của một toán tử đóng:

Bao lồi của một tập X bất kỳ là một tập cha của X.
Với hai tập hợp X và Y sao cho X \subseteq Y thì bao lồi của X là tập con của bao lồi của Y.
Với mọi tập hợp X, bao lồi của bao lồi của X bằng bao lồi của X.

Khi được áp dụng cho một tập hợp hữu hạn các điểm, đó chính là toán tử đóng của một antimatroid, cụ thể là antimatroid bao của tập hợp đó. Mỗi antimatroid đều có thể được biểu diễn theo cách này bằng bao lồi của các điểm trong một không gian Euclid với số chiều đủ lớn.

Tổng Minkowski
Các phép toán dựng bao lồi và tính tổng Minkowski giao hoán lẫn nhau vì tổng Minkowski của bao lồi của các tập hợp có cùng kết quả với bao lồi của tổng Minkowski của các tập hợp đó. Kết luận này là một bước để chứng minh định lý Shapley–Folkman giới hạn khoảng cách giữa một tổng Minkowski và bao lồi của nó.

Đối ngẫu xạ ảnh
Phép đối ngẫu xạ ảnh để dựng bao lồi của một tập hợp hữu hạn các điểm chính là phép dựng giao của một họ gồm các nửa không gian đóng chứa điểm gốc (hoặc một điểm bất kỳ xác định).

Trường hợp đặc biệt

Tập hợp điểm hữu hạn

Bao lồi của một tập hợp điểm hữu hạn S \subset \R^d tạo thành một đa giác lồi khi d = 2, hoặc tổng quát hơn là một đa diện lồi trong \R^d. Mỗi điểm cực biên của bao đó được gọi là đỉnh, và (theo định lý Krein–Milman) mỗi đa diện lồi đều là bao lồi của các đỉnh của nó. Nó chính là đa diện lồi duy nhất có các đỉnh thuộc S và bao hết toàn bộ S. Bao lồi của một đa giác đơn trong mặt phẳng có thể được dựng trong thời gian tuyến tính.

Các cấu trúc dữ liệu bao lồi động có thể được dùng để theo dõi bao lồi của một tập hợp điểm khi thêm vào hoặc xóa đi các điểm trong tập hợp, và các cấu trúc bao lồi điểm chuyển động có thể giúp theo dõi bao lồi đối với các điểm chuyển động liên tục. Dựng bao lồi cũng là công cụ cho một số thuật toán hình học tính toán khác, chẳng hạn như thuật toán thước cặp quay dùng để tính chiều dài và đường kính của một tập hợp điểm.

Các cấu trúc liên quan

Một số hình khác có thể được xác định từ một tập hợp các điểm theo cách tương tự như với bao lồi, có thể là tập cha nhỏ nhất với tính chất nhất định, là giao của tất cả các hình chứa các điểm đó từ một họ các hình cho trước, hoặc là hợp của tất cả tổ hợp của các điểm với dạng nhất định. Ví dụ:

Bao afin là không gian con afin nhỏ nhất của một không gian Euclid chứa một tập hợp cho trước, hoặc là hợp của tất cả tổ hợp afin của các điểm trong tập hợp đó.
Bao tuyến tính là không gian con tuyến tính nhỏ nhất của một không gian vectơ chứa một tập hợp cho trước, hoặc là hợp của tất cả tổ hợp tuyến tính của các điểm trong tập hợp đó.
Bao lồi tương đối của một tập con của một đa giác đơn hai chiều là giao của tất cả các tập cha lồi tương đối, trong đó một tập hợp nằm trong đa giác đó là tập lồi tương đối nếu nó chứa đường trắc địa giữa hai điểm bất kỳ của nó.
Bao lồi trực giao là giao của tất cả các tập cha lồi trực giao được nối lại với nhau, trong đó một tập hợp được gọi là tập lồi trực giao nếu nó chứa tất cả các đoạn thẳng song song với trục tọa độ nối từng cặp điểm có trong nó.
Bao lồi trực giao là một trường hợp đặc biệt của một dạng cấu trúc tổng quát hơn, bao siêu lồi, vốn có thể được xem là không gian mêtric đơn ánh nhỏ nhất chứa các điểm của một không gian mêtric cho trước.
Bao lồi chỉnh hình là một dạng khái quát hóa của các khái niệm tương tự sang đa tạp giải tích phức, có được do nó là giao của các tập mức con của các hàm chỉnh hình chứa một tập hợp cho trước.

Tam giác đạc Delaunay của một tập hợp điểm và dạng đối ngẫu của nó, sơ đồ Voronoi, đều có liên quan đến bao lồi: tam giác đạc Delaunay của một tập hợp điểm trên \R^n có thể được xem là hình chiếu của một bao lồi trên \R^{n+1}. Các hình alpha của một tập hợp điểm hữu hạn cho một họ gồm các đối tượng hình học (không lồi) lồng nhau mô tả hình dạng của một tập hợp điểm tại các cấp độ chi tiết khác nhau. Mỗi hình alpha đều là hợp của một số điểm trong tam giác đạc Delaunay, được chọn bằng cách so sánh bán kính đường tròn ngoại tiếp của chúng với tham số alpha. Chính tập hợp điểm đó tạo thành một điểm cuối của họ các hình đó, và bao lồi của nó tạo thành điểm cuối còn lại. Bao lồi và đa thức cũng có liên hệ với nhau trong định lý Gauss–Lucas, theo đó mọi nghiệm của đạo hàm của một đa thức đều nằm trong bao lồi của các nghiệm của đa thức đó.

Trong lý thuyết phổ, miền số của một ma trận chuẩn tắc là bao lồi của các giá trị riêng của nó. Định lý Russo–Dye mô tả bao lồi của các phần tử đơn nguyên đơn vị trong một C-đại số. Trong hình học rời rạc, định lý Radon và định lý Tverberg có liên quan đến sự tồn tại phân hoạch của các tập hợp điểm thành các tập con với bao lồi giao nhau.

Định nghĩa tập lồi là tập hợp chứa tất cả các đoạn thẳng nối các điểm của nó và bao lồi là giao của tất cả các tập cha lồi đều áp dụng được cho không gian hyperbol và không gian Euclid. Tuy nhiên, trong không gian hyperbol, còn có thể xét đến bao lồi của tập hợp điểm lý tưởng gồm những điểm không thuộc chính không gian hyperbol mà chỉ nằm trong đường biên của một mô hình không gian đó. Đường biên của bao lồi của các điểm lý tưởng của không gian hyperbol ba chiều là tương tự với bề mặt xiên trong không gian Euclid, và các tính chất mêtric của chúng đóng vai trò quan trọng trong giả thuyết hình học hóa trong tôpô ít chiều. Bao lồi hyperbol cũng được dùng khi tính tam giác đạc chính tắc của đa tạp hyperbol, hay xác định xem hai nút thắt có bằng nhau hay không.

Xem thêm mục chuyển động Brown về ứng dụng của bao lồi trong chuyển động Brown, và mục đường cong không gian về ứng dụng của bao lồi trong lý thuyết về bề mặt khai triển được.

Thống kê

Trong thống kê chuẩn mạnh, bao lồi là một trong những thành phần chủ chốt của một bagplot, một phương pháp để minh họa phân bố của các điểm mẫu hai chiều. Các hình bao của độ sâu Tukey tạo thành một họ tập lồi lồng nhau với bao lồi nằm ngoài cùng, và bagplot cũng hiển thị một đa giác khác có hình bao với độ sâu 50% từ họ lồng nhau đó.

Trong lý thuyết quyết định thống kê, tập nguy cơ của một quy tắc ra quyết định ngẫu nhiên là bao lồi của các điểm nguy cơ của các quy tắc ra quyết định tất định nằm dưới nó.

Tối ưu hóa tổ hợp
Đối tượng nghiên cứu trọng tâm trong tối ưu hóa tổ hợp và tổ hợp đa diện là bao lồi của vectơ chỉ thị của nghiệm cho một bài toán tổ hợp. Nếu mặt của các đa diện đó có thể tìm được, mô tả đa diện là giao của các nửa không gian, thì các thuật toán dựa trên quy hoạch tuyến tính có thể được dùng để tìm nghiệm tối ưu. Bao lồi của các vectơ trọng số của các nghiệm đó, một dạng khác của bao lồi, cũng được dùng trong tối ưu hóa đa mục tiêu. Ta có thể cực đại hóa bất kỳ tổ hợp tựa lồi của các trọng số bằng cách tìm và kiểm tra từng đỉnh của bao lồi, hiệu quả hơn nhiều so với khi kiểm tra tất cả các nghiệm có thể có.

Kinh tế
Trong mô hình Arrow–Debreu của cân bằng kinh tế tổng thể, đại diện kinh tế được giả thiết là có tập ngân sách lồi và ưa thích lồi. Các giả thiết này của tính lồi trong kinh tế có thể được dùng để chứng minh sự tồn tại của một cân bằng như thế. Khi dữ liệu kinh tế trong thực tế là phi lồi thì có thể chuyển dữ liệu này sang trạng thái lồi bằng cách lấy bao lồi của nó. Định lý Shapley–Folkman có thể được áp dụng để chứng minh rằng với các thị trường lớn thì phép xấp xỉ này là chính xác và dẫn đến một "tựa cân bằng" đối với thị trường phi lồi ban đầu.

Mô hình hóa hình học
Trong mô hình hóa hình học, một trong những tính chất then chốt của đường cong Bézier là nó nằm trong bao lồi của các điểm kiểm soát của nó. Cái gọi là "đặc tính bao lồi" này có thể được áp dụng để nhanh chóng tìm ra giao điểm của các đường cong như vậy chẳng hạn.

Trong thiết kế tàu thuyền, chu vi xích thân tàu (chain girth) là một độ đo kích thước của một tàu buồm, được xác định bằng bao lồi của mặt cắt ngang thân tàu. Nó khác với chu vi mặt ngoài thân tàu (skin girth) là chu vi của chính mặt cắt đó ngoại trừ đối với tàu thuyền có bao lồi.

Tập tính học
Bao lồi thường được xem là đa giác lồi nhỏ nhất trong tập tính học, một lĩnh vực nghiên cứu hành vi của động vật, ở đó nó là cách tiếp cận cổ điển để ước lượng phạm vi chỗ ở của một loài động vật dựa vào các điểm mà loài động vật đó được quan trắc. Các điểm ngoại lai có thể làm kích thước của đa giác đó tăng một cách quá mức; một hướng tiếp cận khác để hạn chế tình trạng này là chỉ ước lượng dựa trên tập con của các điểm quan trắc, chẳng hạn như chọn một trong các lớp lồi sát với một tỉ lệ mật độ điểm dữ liệu làm mẫu, hoặc áp dụng phương pháp bao lồi địa phương bằng cách hợp bao lồi của láng giềng của các điểm.

Vật lý lượng tử
Trong vật lý lượng tử, không gian trạng thái của một hệ thống lượng tử — tập hợp tất cả các cách hệ thống có thể được thiết lập — là một bao lồi có điểm cực biên là các toán tử nửa xác định dương gọi là trạng thái thuần và các điểm ở phía trong gọi là trạng thái hỗn hợp. Định lý Schrödinger–HJW chứng minh rằng một trạng thái hỗn hợp bất kỳ có thể được viết thành tổ hợp lồi của các trạng thái thuần theo nhiều cách khác nhau.

Nhiệt động lực học
–carbon. Trong ví dụ này Mg2C3 được dự đoán là không bền do nó nằm ở phía trên bao đó.]]
Một bao lồi trong nhiệt động lực học đã được Josiah Willard Gibbs xác định trong bài báo năm 1873, dù nó được xuất bản từ trước khi thuật ngữ "bao lồi" có tên gọi như hiện tại. Trong một tập hợp các mức năng lượng của các hệ số tỷ lượng đối với một vật liệu, chỉ có mức năng lượng với những giá trị đo nằm ở bao lồi dưới mới bền vững. Khi loại đi một điểm thì khoảng cách của nó tới bao này chỉ độ bền của trạng thái đó.

Lịch sử
Bao lồi của các điểm trong mặt phẳng xuất hiện lần đầu tiên dưới dạng đa giác Newton trong thư của Isaac Newton gửi Henry Oldenburg vào năm 1676. Thuật ngữ convex hull trong tiếng Anh xuất hiện sớm nhất từ công trình của , và cụm từ tương ứng trong tiếng Đức xuất hiện sớm hơn, chẳng hạn như trong bình duyệt về của Hans Rademacher. Một số thuật ngữ khác như convex envelope cũng được sử dụng trong khoảng thời gian này. Đến năm 1938, theo Lloyd Dines, từ convex hull đã trở thành tiêu chuẩn, và Dines thêm rằng ông thấy đó là điều đáng tiếc, vì nghĩa thông tục của từ hull có thể được hiểu rằng nó chỉ bề mặt của một hình, trong khi bao lồi thực tế còn chứa thêm cả phần bên trong chứ không chỉ có phần bề mặt đó.

Chú thích

Tham khảo

; in lại trong The Scientific Papers of J. Willard Gibbs, Vol. I: Thermodynamics, Longmans, Green, & Co., 1906, tr. 33–54

; xem thêm bình duyệt của Hans Rademacher (1922),

, translated in Journal of Soviet Mathematics 33 (4): 1140–1153, 1986,

Đọc thêm

. Đặc biệt xem mục "1.1.2 Bao lồi và bao lồi đóng", tr. 6–9.

Liên kết ngoài