Efficient Chamfer Distance | Dataford Interview Questions

Your question is Efficient Chamfer Distance. Start with the requirements on the right.

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

Problem

Amazon Advertising systems may compare sets of vectors representing ad creatives, audience segments, or retrieved candidates. Given two nonempty point clouds, compute their symmetric Chamfer distance efficiently instead of comparing every cross-cloud pair.

For point clouds A and B, where each point has d coordinates, define:

D(A, B) = (1 / |A|) * sum(minimum squared Euclidean distance from a in A to any point in B)) + (1 / |B|) * sum(minimum squared Euclidean distance from b in B to any point in A))

Implement chamfer_distance(points_a, points_b) and return the distance as a floating-point number. The implementation must use an exact nearest-neighbor data structure, such as a KD-tree, rather than constructing all |A| * |B| pairwise distances.

Constraints

1 <= len(points_a), len(points_b) <= 50,000
1 <= len(point) <= 10
Both point clouds have equal dimensionality
-10^6 <= coordinate <= 10^6
Use squared Euclidean distance
Return a result accurate within 1e-9 relative or absolute error

Function Signature

def chamfer_distance(points_a, points_b):