Quad Tree merupakan algoritma yang menggunakan konsep tree untuk menyimpan data berupa titik dalam bidang dua dimensi. Pada tree ini, setiap node akan memiliki maksimal empat node anak. Quad tree ini dapat digunakan untuk mencari titik terdekat secara efisien terhadap sebuah posisi yang diinginkan.

More trees: balanced BSTs and specialized treesGambar 1. Representasi quad tree.
Sumber Gambar: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/moretrees.php 

Pada Gambar 1 sebelah kanan merupakan bidang dua dimensi yang berisi 6 titik (A, B, C, D, E, F) yang selanjutnya dilakukan partitioning dengan quad tree. Pada sebelah kiri merupakah quad tree yang terbentuk berdasarkan hasil partitioning bidang dua dimensi.

Pada BITS Authoring Tool Editor, saya mengimplementasikan quad tree ini untuk memberikan rekomendasi objek terdekat yang dapat disejajarkan. Setiap objek di BITS merupakan kontainer yang berupa bentuk persegi terdiri dari 4 titik. Quad tree digunakan untuk menyimpan seluruh koordinat kontainer yang telah ditambahkan ke dalam editor. Ketika sebuah kontainer digeser ke arah tertentu atau salah satu sisi kontainer ditarik ke arah tertentu, maka akan dilakukan pencarian titik terdekat dari kontainer lain (Gambar 2).

Gambar 2. Implementasi rekomendasi kontainer terdekat pada BITS Editor

Menurut notasi asymptotic proses pencarian ini adalah O(lg n) baca: log basis 2 dari N, dimana N adalah banyaknya titik pada quad tree. Misalnya pada sebuah halaman konten terdapat 20 kontainer, berarti 20 x 4 titik = 80 titik. ketika ingin mencari jarak terdekat terhadap titik tertentu, maka hanya perlu dilakukan log basis 2 dari 80 yaitu 7 kali proses (6.3 dibulatkan ke atas). Hal ini tentu sangat efisien dibanding melakukan perbandingan naive terhadap semua 80 titik dan dicari yang terdekat.

Referensi:
http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/moretrees.php
https://www.geeksforgeeks.org/quad-tree/
https://jimkang.com/quadtreevis/