Convex Hull Boundary Engine — Problem Statement & Solution Guide

GraphsHardHeavy-Light Decomposition

TimeO((log N)^2) per query, O(N log N) preprocessing

SpaceO(N log N) for hull storage

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Graphs and solve the Convex Hull Boundary Engine 2 problem optimally.

TopicGraphs

PatternHeavy-Light Decomposition

TimeO((log N)^2) per query, O(N log N) preprocessing

SpaceO(N log N) for hull storage

Problem Description

You are given an undirected tree with N vertices numbered from 1 to N. Vertex i is associated with a point Pi = (xi, yi) in the 2‑dimensional Cartesian plane. The tree is described by N‑1 edges. After building the tree you must answer Q independent queries. Each query provides two vertices u and v. Consider the unique simple path between u and v in the tree and collect all points belonging to the vertices on this path. Compute the convex hull of this point set and output the number of distinct vertices that appear on the hull (points that lie strictly inside the hull are not counted). The convex hull must be defined in the usual geometric sense (the smallest convex polygon containing all points). If all points on the path are collinear, the hull consists of the two extreme points, so the answer is 2 (or 1 if the path contains a single vertex). Implement an algorithm that processes all queries efficiently; a typical solution employs Heavy‑Light Decomposition to break each path into O(log N) segments and merges pre‑computed hull information for each segment.

DSA Pattern Breakdown

"Convex Hull Boundary Engine"

hard

WHY DOES IT MATTER?

Binary lifting with precomputed convex hulls transforms a potentially linear‑time path query into a logarithmic‑time operation, which is critical when handling up to 10^5 queries on large trees. Without this pattern, the algorithm would not scale.

OPTIMIZATION CHALLENGE

The key insight is that convex hulls can be merged in linear time, allowing us to combine O(log N) precomputed hulls per query without recomputing from scratch. This reduces both time and space compared to naive per‑vertex processing.

REAL-WORLD CONNECTION

Think of a distributed system where each node caches aggregated statistics of its subtree. When a request traverses a path, the system merges cached summaries from O(log N) nodes, analogous to merging convex hulls from binary‑lifted ancestors.

When implementing the hull merge, always sort the hull vertices by polar angle once and reuse the sorted order during binary lifting to avoid repeated sorting overhead.

COMPLEXITY AT A GLANCE

⏱ Time:O((log N)^2) per query, O(N log N) preprocessing

💾 Space:O(N log N) for hull storage

Core Theory — Why This Approach?

The problem asks for the convex hull of all points lying on the unique simple path between two vertices in a tree. A naive solution would enumerate every vertex on the path, collect its coordinates, and compute the convex hull in O(k log k) time, where k is the path length. In the worst case k can be O(N), leading to O(N log N) per query, which is infeasible for large N and Q.

The optimal paradigm leverages the tree’s hierarchical structure and binary lifting. For each node v and each power of two 2^k, we precompute the convex hull of the vertices on the path from v up to its 2^k‑th ancestor. These hulls are stored in a binary‑lifting table H[v][k]. Merging two convex hulls can be done in linear time relative to their sizes using the standard Graham scan merge technique. To answer a query (u, v), we first find their lowest common ancestor (LCA). The path u→v is split into u→LCA and LCA→v. For each side we climb from the node to the LCA, collecting O(log N) precomputed hulls and merging them incrementally. The total work per query is O((log N)^2) time and O(log N) additional space, which is optimal for the constraints.

This approach reduces the per‑query complexity from linear in the path length to logarithmic in the tree size, making it suitable for up to 10^5 vertices and queries.

Interview Questions on This Problem

Q1How would you modify the binary lifting convex hull approach if the tree were directed and you needed to answer queries for paths that are not necessarily simple?

In a directed acyclic graph, the notion of a unique simple path may not exist. One would need to precompute all possible paths or use dynamic programming on DAGs. For convex hull queries, a feasible strategy is to compute convex hulls for all reachable nodes from each source using a topological order and maintain hulls in a segment tree or Fenwick tree. However, this quickly becomes infeasible for large graphs, so the interviewer would expect a discussion of the limitations and possible heuristic approximations.

Q2A fintech platform wants to compute the convex hull of transaction locations along a referral chain. What data structure would you recommend to support real‑time updates and queries?

A balanced binary search tree (e.g., AVL or Red‑Black) augmented with convex hull information can support insertions, deletions, and hull queries in O(log N) time. Each node stores the convex hull of its subtree, and merging hulls during rotations keeps the structure updated. For a referral chain, which is essentially a tree, this structure allows dynamic updates while preserving query efficiency.

Q3During a coding interview at a high‑growth startup, you are asked to explain why merging convex hulls is linear. Can you provide a concise proof?

When merging two convex hulls A and B, we first concatenate their vertex lists sorted by polar angle. Then we run a single pass of the Graham scan, which processes each vertex once and performs a constant number of stack operations. Since each vertex is examined a constant number of times, the total time is linear in |A|+|B|.

Examples

Example 1

Input

Output

3
3
3

Explanation: The tree has 5 vertices with the given coordinates. Edges connect (1‑2), (2‑3), (3‑4) and (3‑5). Query 1: path 1‑2‑3‑5 contains points (0,0), (2,0), (1,1), (2,2). Their convex hull is the triangle with vertices (0,0), (2,0) and (2,2); therefore the answer is 3. Query 2: path 4‑3‑5 contains points (0,2), (1,1), (2,2). These three points are not collinear, so all of them belong to the hull; answer = 3. Query 3: path 2‑3‑4 contains points (2,0), (1,1), (0,2). Again the three points form a triangle, giving answer = 3.

Example 2

Input

Output

Explanation: Vertices are the corners of a square. The unique path from 1 to 4 visits vertices 1‑2‑3‑4, i.e., points (0,0), (4,0), (4,4), (0,4). Their convex hull is the square itself, which has 4 distinct vertices, so the answer is 4.

Example 3

Input

Output

2
1

Explanation: All three points lie on the x‑axis. Query 1 asks for the path 1‑2‑3, whose points are collinear; the hull consists of the two extreme points (0,0) and (2,0), so the answer is 2. Query 2 asks for the path consisting of a single vertex 2; the hull contains only that point, therefore the answer is 1.

Constraints

1 <= N <= 2*10^5
1 <= Q <= 2*10^5
-10^9 <= xi, yi <= 10^9
The given edges form a connected acyclic graph (a tree).

Optimal Approach & Strategy

Precompute convex hulls for binary‑lifted ancestor paths; answer queries by merging O(log N) hulls, achieving O((log N)^2) time per query.

Brute Force Approach

Collect all vertices on the path between u and v, then compute their convex hull using a standard algorithm in O(k log k) time, where k is the path length.

Code Solutions

Language:

JavaScript Solution

Time: O((log N)^2) per query, O(N log N) preprocessing

function convexHull(points) {
  points.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
  let hull = [points[0], points[1]];
  for (let i = 2; i < points.length; i++) {
    while (hull.length > 1 && crossProduct(hull[hull.length - 2], hull[hull.length - 1], points[i]) <= 0) {
      hull.pop();
    }
    hull.push(points[i]);
  }
  return hull;
}

function crossProduct(p1, p2, p3) {
  return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
}

class Solution {
public:
  int* convexHull(int** points, int pointsSize) {
    std::sort(points, points + pointsSize, [](int* a, int* b) {
      return (a[0] - a[1]) - (b[0] - b[1]);
    });
    int* hull = new int[4];
    hull[0] = points[0][0];
    hull[1] = points[0][1];
    hull[2] = points[1][0];
    hull[3] = points[1][1];
    for (int i = 2; i < pointsSize; i++) {
      while (hull[2] && crossProduct(hull[hull[2] - 2], hull[hull[2] - 1], points[i]) <= 0) {
        hull[2]--;
      }
      hull[2]++;
      hull[hull[2]] = points[i][0];
      hull[hull[2] + 1] = points[i][1];
    }
    return hull;
  }

  int crossProduct(int* p1, int* p2, int* p3) {
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
  }
}

class Solution {
  public int[] convexHull(int[][] points) {
    Arrays.sort(points, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
    int[] hull = new int[2];
    hull[0] = points[0][0];
    hull[1] = points[0][1];
    hull[2] = points[1][0];
    hull[3] = points[1][1];
    for (int i = 2; i < points.length; i++) {
      while (hull.length > 2 && crossProduct(hull[hull.length - 2], hull[hull.length - 1], points[i]) <= 0) {
        hull = Arrays.copyOfRange(hull, 0, hull.length - 1);
      }
      hull = Arrays.copyOf(hull, hull.length + 1);
      hull[hull.length - 1] = points[i][0];
      hull[hull.length] = points[i][1];
    }
    return hull;
  }

  public int crossProduct(int[] p1, int[] p2, int[] p3) {
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
  }
}

def convex_hull(points):
  points.sort(key=lambda x: (x[0] - x[1], x[0]))
  hull = [points[0], points[1]]
  for i in range(2, len(points)):
    while len(hull) > 1 and cross_product(hull[-2], hull[-1], points[i]) <= 0:
      hull.pop()
    hull.append(points[i])
  return hull

def cross_product(p1, p2, p3):
  return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

function convexHull(points) {
  points.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
  let hull = [points[0], points[1]];
  for (let i = 2; i < points.length; i++) {
    while (hull.length > 1 && crossProduct(hull[hull.length - 2], hull[hull.length - 1], points[i]) <= 0) {
      hull.pop();
    }
    hull.push(points[i]);
  }
  return hull;
}

function crossProduct(p1, p2, p3) {
  return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
}

Asked in Top Tech Interviews

AtlassianMorgan Stanley

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.