Xem mẫu
Chương 4:
Các giải thuật hình học
Computational Geometry
PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ
1 2013
Dữ liệu nhiều chiều
Các giải thuật hình học liên quan tới dữ liệu không gian đa chiều.
– Một điểm trong mặt phẳng (x,y)
– Một điểm trong không gian (x,y,z)
Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều.
Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiều
Một số bài toán quan trọng
– Tìm kiếm theo phạm vi (range searching query)
– Tìm bao lồi (convex hull)
2
Cây tìm kiếm phạm vi
Một điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1,…,xd-1).
Tìm kiếm theo phạm vi là tìm kiếm các điểm trong một phạm vi nào đó.
– Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r)
Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi.
– Ví dụ tìm các điểm gần với (xq,yq) trong khoảng cách r.
3
Tìm kiếm 1 chiều theo phạm vi
Cho một tự điển (tập hợp các phần tử) có thứ tự
findAllInRange(k1,k2): trả về các phần tử thỏa:
– k1 ≤ x ≤ k2
Dùng cấu trúc cây TKNP để lưu trữ các phần tử
Giải thuật tìm kiếm 1DTreeRangeSearch(k1,k2,v)
– Nếu v là nút ngoài (V=NULL): dừng
– Nếu v là nút trong
Key(v)k2: tìm đệ qui trên cây con trái của v.
4
Giải thuật 1DTreeRangeSearch
1DTreeRangeSearch(k1,k2,v){ if v.isExternal(v) return ; if (k1 ≤ key(v) ≤ k2) {
L= 1DTreeRangeSearch(k1,k2,T.leftChild(v)); R= 1DTreeRangeSearch(k1,k2,T.rightChild(v)); return L U {element(v)} U R;
}
else if (key(v)
nguon tai.lieu . vn