Lưới ε (hình học tính toán)

Đối với các định nghĩa khác, xem Lưới ε.

Trong hình học tính toán, lưới ε là một khái niệm về việc xấp xỉ một tập hợp điểm cho trước bằng một tập hợp nhỏ hơn.

Định nghĩa

Một lưới ε với ε=1/4 của hình vuông đơn vị và tập hợp các vùng là các hình chữ nhật

Giả sử X là một tập hợp điểm và R là một tập hợp các tập hợp con của X. Một cặp (X, R) như vậy tạo thành một không gian vùng hay một siêu đồ thị. Mỗi phần tử của R gọi là một vùng hay một siêu cạnh. Một lưới ε (hay lưới ε mạnh) của một tập hợp con P của X là một tập hợp con N của P sao cho mọi tập hợp r ∈ R thỏa mãn |r ∩ P| ≥ ε|P| đều giao với N.^[1] Nói cách khác, mọi vùng có chứa ε lực lượng của P đều giao với lưới ε N. Nếu loại bỏ điều kiện N là tập hợp con của P thì đó gọi là một lưới ε yếu của P.

Chẳng hạn, xét X là tập hợp các điểm trên mặt phẳng 2 chiều, R là tập hợp các hình chữ nhật đóng song song trục tọa độ (tích của hai khoảng đóng), và P là hình vuông đơn vị [0, 1] × [0, 1]. Khi đó tập hợp N bao gồm 8 điểm như trong hình vẽ bên phải là một lưới 1/4 của P, vì mọi hình chữ nhật đóng có chứa 1/4 diện tích hình vuông đơn vị đều giao với tập hợp điểm này. Tổng quát hơn, mọi hình vuông song song trục tọa độ, bất kể kích thước bao nhiêu, đều có một lưới 1/4 gồm 8 điểm tương tự như vậy.

Với mọi không gian vùng có chiều VC d, với mọi P và ε, đều tồn tại lưới ε của P có kích thước

${\displaystyle O\left({\frac {d}{\varepsilon }}\log {\frac {d}{\varepsilon }}\right);}$

Vì kích thước tập hợp này không phụ thuộc vào P, mọi tập hợp P đều có được mô tả bằng một tập hợp kích thước như vậy.

Lưới ε được sử dụng trong việc xây dựng thuật toán xấp xỉ cho nhiều bài toán NP-đầy đủ chẳng hạn như bài toán phủ tập hợp.^[2]

Xem thêm

• Xấp xỉ ε

Tài liệu tham khảo

1. Haussler, David; Welzl, Emo (1987), “ε-nets and simplex range queries”, Discrete and Computational Geometry, 2 (2): 127–151, doi:10.1007/BF02187876, MR 0884223.
2. Brönnimann, H.; Goodrich, M. T. (1995), “Almost optimal set covers in finite VC-dimension”, Discrete and Computational Geometry, 14 (4): 463–479, doi:10.1007/BF02570718, MR 1360948, Bản gốc lưu trữ ngày 28 tháng 1 năm 2012, truy cập ngày 17 tháng 3 năm 2012.