Tìm kiếm vùng

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Tìm kiếm vùng đơn hình.

Dạng tổng quát nhất của bài toán tìm kiếm vùng là như sau: xử lý và lưu trữ một tập hợp S các đối tượng, sao cho có thể xác định xem một vùng cho trước chứa những đối tượng nào trong S. Chẳng hạn S có thể là một tập hợp các điểm tương ứng với tọa độ của các thành phố, và ta muốn tìm xem có những thành phố nào trong khoảng kinh độvĩ độ cho trước.

Bài toán tìm kiếm vùng và các cấu trúc dữ liệu cho nó là những vấn đề cơ bản của hình học tính toán. Bài toán tìm kiếm vùng không chỉ có ứng dụng trong xử lý dữ liệu hình học (như trong hệ thống thông tin địa lý (GIS) hay CAD, mà còn trong cơ sở dữ liệu nói chung.

Các biến thể[sửa | sửa mã nguồn]

Có nhiều biến thể khác nhau của bài toán này, và các biến thể khác nhau đòi hỏi các cấu trúc dữ liệu khác nhau. Để có được lời giải hiệu quả, cần xác định các yếu tố sau của bài toán:

Tham khảo[sửa | sửa mã nguồn]