Tìm kiếm vùng

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à 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ể

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:

  • Loại đối tượng: thuật toán tùy thuộc vào S bao gồm các điểm, đường thẳng, đoạn thẳng, hình chữ nhật, đa giác,... Đối tượng đơn giản nhất và cũng được nghiên cứu nhiều nhất là điểm.
  • Loại vùng: Các vùng cần tìm phải thuộc một thể loại nhất định. Một vài thể loại được nghiên cứu cùng với tên của bài toán tương ứng bao gồm hình chữ nhật song song trục tọa độ (tìm kiếm vùng trực giao), đơn hình (tìm kiếm vùng đơn hình), nửa không gian (tìm kiếm vùng nửa không gian), và hình cầu (tìm kiếm vùng hình cầu).
  • Loại câu hỏi: có một số loại câu hỏi khác nhau thường được nghiên cứu: liệt kê tất cả các đối tượng trong vùng, đếm số đối tượng trong vùng, kiểm tra xem có tồn tại đối tượng nào trong vùng hay không.
  • Tìm kiếm vùng động và tìm kiếm vùng tĩnh: trong trường hợp tĩnh, tập hợp S được biết ngay từ đầu và không thay đổi. Trong trường hợp động, tập hợp S có thể được chèn thêm hoặc xóa bớt giữa các câu hỏi.
  • Tìm kiếm vùng offline: cả tập hợp đối tượng và tập hợp các câu hỏi được biết đến ngay từ đầu.

Tham khảo

  • Agarwal, P. K.; Erickson, J. (1999), “Geometric Range Searching and Its Relatives”, trong Chazelle, Bernard; Goodman, Jacob; Pollack, Richard (biên tập), Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College (PDF), Contemporary Mathematics, 223, American Mathematical Society Press, tr. 1–56, Bản gốc (PDF) lưu trữ ngày 29 tháng 6 năm 2011, truy cập ngày 24 tháng 9 năm 2011.
  • de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry (ấn bản 2), Berlin: Springer-Verlag, ISBN 3-540-65620-0. Xem chương 5 và 16.
  • Matoušek, Jiří (1994), “Geometric range searching”, ACM Computing Surveys, 26 (4): 421–461.