Group points by distance threshold

Problem Statement

You are given a list of 2D points points represented as [x, y] coordinates and a positive float threshold. Two points belong to the same group if the Euclidean distance between them is less than or equal to threshold. If point A is connected to point B, and point B is connected to point C, then A, B, and C all belong to the same group (transitive property).

Write a function group_points(points, threshold) that returns a list of lists, where each inner list contains the indices of the points that form a distinct group.

Function Signature

def group_points(points: List[List[float]], threshold: float) -> List[List[int]]:

Constraints

• 1 <= len(points) <= 1000
• -10^4 <= x, y <= 10^4
• 0 <= threshold <= 10^4

Examples

Example 1: Input: points = [[0,0], [1,0], [5,5], [6,5]], threshold = 1.5 Output: [[0, 1], [2, 3]] Explanation: [0,0] and [1,0] have distance 1.0 (<= 1.5). [5,5] and [6,5] have distance 1.0 (<= 1.5). No other pairs meet the criteria.

Example 2: Input: points = [[0,0], [1,1], [2,2]], threshold = 1.5 Output: [[0, 1, 2]] Explanation: Distance between [0,0] and [1,1] is ~1.41. Distance between [1,1] and [2,2] is ~1.41. Since both are <= 1.5, they form a single group.

Edge Cases

• A point with no neighbors should be in its own group.
• threshold = 0 (only identical points are grouped).