Tripos 2023 Paper 1 Question 2 — Worked Solution

Question: Quadtrees of points.

type point = int * int
type qt = Empty | Quad of qt * qt * point * qt * qt

A Quad(nw, ne, (x,y), sw, se) contains points in quadrants around (x,y). x is the right bound of points in nw and sw; left bound of points in ne and se. y is the upper bound of points in sw and se; lower bound of points in nw and ne.

(a) compare_range [2 marks]

type range = int * int
type rel = LT | IN | GT

let compare_range v (lo, hi) =
  if v < lo then LT
  else if v > hi then GT
  else IN

Explanation: We compare v against the inclusive range [lo, hi]. Three cases: below the range (LT), within it (IN), or above it (GT). The function is O(1). For compare_range 3 (2,5), since 2 ≤ 3 ≤ 5, the result is IN.

(b) has_point [8 marks]

Efficiently search a quadtree for a specific point.

let rec has_point (px, py) = function
  | Empty -> false
  | Quad (nw, ne, (x, y), sw, se) ->
      if px = x && py = y then true
      else if px <= x then
        if py <= y then has_point (px, py) nw
        else has_point (px, py) sw
      else
        if py <= y then has_point (px, py) ne
        else has_point (px, py) se

Explanation: The quadtree partitions 2D space around the point (x, y). To search:

1. If the tree is Empty, the point is not present.

2. If the current node’s point matches (px, py), return true.

3. Otherwise, determine which quadrant the search point falls into:

   • North-West (nw): px ≤ x and py ≤ y (left of or equal to x, below or equal to y).
   • South-West (sw): px ≤ x and py > y.
   • North-East (ne): px > x and py ≤ y.
   • South-East (se): px > x and py > y.

4. Recursively search only that one quadrant. This is the key to efficiency: we prune three-quarters of the remaining space at each step. For a balanced quadtree with n points, the depth is O(log n), so search takes O(log n) time — analogous to binary search in a 1D BST but extended to 2D.

Note the ≤ on the boundaries: points with px = x go to the left (nw or sw), and points with py = y go below (nw or ne). This matches the problem statement (“x is the right bound of points in nw and sw” meaning nw/sw contain points where px ≤ x).

(c) has_point_in [10 marks]

Search for any point within a rectangular region.

type rectangle = point * point

let rec has_point_in ((x1, y1), (x2, y2)) = function
  | Empty -> false
  | Quad (nw, ne, (x, y), sw, se) ->
      let px_in = compare_range (fst (x, y)) (x1, x2) in
      let py_in = compare_range (snd (x, y)) (y1, y2) in
      if px_in = IN && py_in = IN then true
      else
        let check_nw = (x1 <= x && y1 <= y) &&
          has_point_in ((x1, y1), (x2, y2)) nw in
        let check_ne = (x2 > x && y1 <= y) &&
          has_point_in ((x1, y1), (x2, y2)) ne in
        let check_sw = (x1 <= x && y2 > y) &&
          has_point_in ((x1, y1), (x2, y2)) sw in
        let check_se = (x2 > x && y2 > y) &&
          has_point_in ((x1, y1), (x2, y2)) se in
        check_nw || check_ne || check_sw || check_se

Better, more readable version:

let rec has_point_in ((x1, y1), (x2, y2)) = function
  | Empty -> false
  | Quad (nw, ne, (x, y), sw, se) ->
      if x1 <= x && x <= x2 && y1 <= y && y <= y2 then true
      else
        let rec check_when cond subtree =
          cond && has_point_in ((x1, y1), (x2, y2)) subtree
        in
        check_when (x1 <= x && y1 <= y) nw ||
        check_when (x2 > x && y1 <= y) ne ||
        check_when (x1 <= x && y2 > y) sw ||
        check_when (x2 > x && y2 > y) se

Explanation: The algorithm is a 2D range query on a quadtree:

1. If the tree is Empty, there is no point in the region.

2. If the current node’s point (x, y) lies within the rectangular region [x1, x2] × [y1, y2], return true immediately.

3. Otherwise, we need to search the quadrants. But we only search a quadrant if it could contain points in the region. The condition for searching each quadrant is that the quadrant’s bounding box overlaps with the query rectangle:

   • NW (points with px ≤ x, py ≤ y): overlaps if x1 ≤ x (region extends into left half) and y1 ≤ y (region extends into lower half).
   • NE (points with px > x, py ≤ y): overlaps if x2 > x (region extends into right half) and y1 ≤ y.
   • SW (points with px ≤ x, py > y): overlaps if x1 ≤ x and y2 > y.
   • SE (points with px > x, py > y): overlaps if x2 > x and y2 > y.

4. The || operator is short-circuiting: we stop searching as soon as we find a point in the region.

Efficiency: In the worst case, the query rectangle covers the entire space and we must search all n points — O(n) time. In practice, for small query regions, we prune most of the tree. If the quadtree is balanced, the number of visited nodes is proportional to the number of points in (or near) the region plus O(log n) for the traversal. The space complexity is O(depth) for the recursion stack. The function correctly returns true if and only if the quadtree contains at least one point lying within the specified rectangular region.