Quad Trees

Question 1

Quad trees motive

Answer 1

Divide a space recursively to be able to get into resolution where needed and to search in space.

Question 2

Point quad tree idea

Answer 2

A quad tree to provide search in 2d space. Each new point divides its space into 4 new spaces and is in the center of these spaces.

Question 3

Point quad tree run time

Answer 3

insert: O(logn)
search: If tree is not weighted than can be linear.
Delete: Very bad, find node, delete and reenter all points in sub tree.

Question 4

PR quad tree

Answer 4

Provides data about certain areas. Each area can hold p points, when p is reached, subdivide the area into 4 new ones and enter there.