Bao lồi

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Convex hull: elastic band analogy

Giới thiệu[sửa | sửa mã nguồn]

Trong toán học, các bao lồi hoặc bao đóng cho một tập hợp các điểm X trong một không gian vector thực V là số lượng tối thiểu các đỉnh để chứa hết X.

Trong hình học máy tính, thuật ngữ "bao lồi" được sử dụng phổ biến chỉ những ranh giới của các tập hợp tối thiểu có chứa một tập hợp không rỗng và chứa trong toàn bộ số điểm. Trừ khi có các điểm thẳng hàng, các bao lồi là một chuỗi các đỉnh tạo thành đa giác.

Hình ảnh trực quan[sửa | sửa mã nguồn]

Với các đối tượng 2 chiều, tức là nằm trong mặt phẳng, các bao lồi có thể dễ dàng giả lập bằng cách hình dung ra một tập hợp mở luôn giãn ra để đưa ra các đối tượng vào bên trong, khi hoàn thành, nó sẽ tạo thành một bao lồi theo đúng yêu cầu.

Có vẻ như thật dễ dàng để đưa tập hợp này lên không gian cao hơn bằng cách tưởng tượng các đối tượng trong một gói co giãn như là bong bóng. Tuy nhiên, sự cân bằng (tối năng lượng tối thiểu) bề mặt trong trường hợp này có thể không phải là bao lồi - do các phần của mặt phẳng kết quả có thể là mặt cong, giống như mặt vòm.

Sự tồn tại của các bao lồi[sửa | sửa mã nguồn]

Để biểu diễn bao lồi của một tập X trong một không gian vector thực V, chú ý X là trong ít nhất một bộ đỉnh (ví dụ toàn bộ không gian V), và bất kỳ tập hợp giao nào của bộ đỉnh chứa X cũng là một bộ đỉnh có chứa X. Điều này có vẻ như là hiển nhiên. Đây có thể được sử dụng như là một định nghĩa thay thế của bao lồi.

Trực tiếp hơn, các bao lồi của X (có thể xây dựng được) được mô tả như là một tập con hữu hạn rút ra từ X có dạng:Tập tin:Http://upload.wikimedia.org/math/2/d/7/2d7a62bfc4a311f73dc658846a2b1124.png. Trong đó, n một số tự nhiên nguyên, t, j không âm và bắt đầu từ 1, và các điểm xj thuộc X. Việc kiểm tra các điểm này có thoả định nghĩa trên hay không thật đơng giản. Vì vậy, các bao lồi Hconvex (X) của bộ X là:

Tập tin:Http://upload.wikimedia.org/math/3/0/9/309de16bdec4708c859954c179ef2901.png

Trong thực tế, nếu X là một tập con trong không gian vectơ N chiều, bao là kết hợp của nhiều nhất là N + 1 điểm là đủ trong theo định nghĩa ở trên. Điều này tương đương với nói rằng bao lồi của X là một đơn hình có nhiều nhất N+1 điểm thuộc X. Định nghĩa này được biết đến như Lý thuyết Carathéodory.

Các bao lồi được xác định cho bất kỳ đối tượng nào tạo nên từ điểm trong một không gian véc tơ, không phụ thuộc vào chiều không gian. Các bao lồi của một bộ hữu hạn các điểm và các đối tượng hình học trong một không gian hai hay ba chiều là những trường hợp đặc biệt có trong thực tế.

Tính số bao lồi[sửa | sửa mã nguồn]

Trong hình học máy tính, rất nhiều các thuật toán đã được đề nghị để xác định bao lồi của một tập hợp các điểm, với độ phức tạp khác nhau, bao gồm:

  • Phương pháp trực tiếp (Direct)
  • Phương pháp đóng gói (Wrapping)
  • Phương pháp Quét Graham (Graham Scan)
  • Phương pháp Tuần tự (Sequel)
  • Phương pháp Chia để trị (Divide and Conquer)
  • Phương pháp Quick (tương tự Quick Sort)
  • Phương pháp xoá điểm bên trong (Inner Point Elimination)

Tính toán bao lồi cấn thiết phải rõ ràng và hiệu quả để xây dựng nên một đa giác lồi theo ý muốn. Sự phức tạp của thuật toán tương ứng thường được ước tính tuỳ theo điều kiện của n, số lượng các điểm đầu vào, và số lượng điểm trên bao lồi.

Xem thêm[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng |
Toán học giải trí | Toán học tô pô | Xác suất thống kê