Can you reach target with distance-threshold edges?
Quick Overview
This question evaluates understanding of graph connectivity and spatial proximity modeling, examining competencies in graph algorithms and computational geometry within the Coding & Algorithms domain relevant for Machine Learning Engineer roles.
You are given a set of unordered 2D points points[], a start point and an end point (both are included in points), and a function:
getDistance(p, q)
that returns the distance between two points p and q.
Define an undirected graph where two points are connected by an edge iff getDistance(p, q) < r for a given threshold r.
Task: Determine whether there exists a path from start to end.
Follow-up: If points is very large and calling getDistance is expensive, how would you reduce repeated distance computations and/or avoid checking all pairs?