Planar dinamis tetangga k-terdekat terdekat untuk data patologis

Apa hasil yang paling dikenal untuk struktur data yang menawarkan operasi berikut pada set poin dalam ruang euclidean 2 dimensi:

• $insert(x)$
• $delete(x)$
• (di mana k adalah bilangan bulat lebih besar dari 0) mengembalikantitik terdekat k ke x yang ada di set.$nearest(k,x)$$k$$k$$x$

Dalam kasus khusus ini, saya tidak terlalu tertarik pada perkiraan tetangga terdekat, algoritma Monte Carlo, atau algoritma yang menganggap data terbentuk dengan baik dalam beberapa cara.

Saya tidak berprasangka terhadap algoritma Las Vegas, algoritma yang menganggap koordinat titik memiliki bit, atau algoritma dengan waktu berjalan tergantung pada k .$O(\lg n)$$k$

$O($$)$$k=1$$O(k$$)$$k$