VuaTenMien.Com: Phần thuật toán của bài lính bắn laser

Thứ Bảy, 19 tháng 3, 2011

Phần thuật toán của bài lính bắn laser

Ta tiếp tục với bài lính bắn laser. Nhờ định lý Loomis-Whitney, ta đã biết điều sau đây. Cho ba tập điểm

$A = \{(x^a_1, y^a_1), \dots, (x^a_k, y^a_k)\}$
$B = \{(y^b_1, z^b_1), \dots, (y^b_k, z^b_k)\}$
$C = \{(z^c_1, x^c_1), \dots, (z^c_k, x^c_k)\}$

thì không tồn tại nhiều hơn $k^{3/2}$ điểm (x,y,z) sao scho $(x,y) \in A$ , $(y, z) \in B$ , và $(z,x) \in C$ . Gọi các điểm này là các điểm ba màu.

Với inputs là A, B, C , để in ra các điểm ba màu thì thời gian chạy O(k^3) là tầm thường. Và, ta biết trong trường hợp tệ nhất thì cần $\Omega(k^{3/2})$ .