Division of Space by Quad-trees

Each node of a quad-tree is associated with a rectangular region of space; the top node is associated with the entire target space. Each non-leaf nodes divides its region into four equal sized quadrants correspondingly each such node has four child nodes corresponding to the four quadrants and so on. Leaf nodes have between zero and some fixed maximum number of points (Fig 2.2: set to 1 in example).