Chamfer Distance for Point Clouds | Dataford Interview Questions

Amazon Kuiper Commercial Services compares reconstructed and reference point clouds from satellite and ground-based sensing pipelines. Given two point clouds, compute their symmetric squared Chamfer distance exactly.

For point clouds A and B, define:

CD(A, B) = 0.5 * (sum(min squared distance from a to B) / len(A) + sum(min squared distance from b to A) / len(B))

Implement chamfer_distance(points_a, points_b) and return the result as a floating-point number. The squared Euclidean distance between points is used, so do not take square roots. Your algorithm should avoid comparing every pair whenever possible.

Formal Specification

Input: Two non-empty lists of points, where every point is a list of 2 or 3 numeric coordinates. Both clouds use the same dimension.
Output: A floating-point symmetric Chamfer distance.
The result must be exact, not an approximation.

Constraints

1 <= len(points_a), len(points_b) <= 50,000
Each point has exactly 2 or 3 coordinates
Both point clouds have the same dimensionality
Coordinates are finite numeric values in [-10^6, 10^6]
Duplicate points are allowed
The output is computed using squared Euclidean distances

Function Signature

def chamfer_distance(points_a, points_b):

Your question is Chamfer Distance for Point Clouds. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem