Loading problem...
In many data-driven applications, determining which data points are most similar to a given reference point is a fundamental operation. This process, known as proximity-based neighbor retrieval, is a cornerstone technique in machine learning, pattern recognition, and spatial data analysis.
Given a collection of points in an n-dimensional space and a query point, your goal is to identify the k points that are closest to the query point based on their Euclidean distance.
Euclidean Distance: The Euclidean distance between two points ( P = (p_1, p_2, ..., p_n) ) and ( Q = (q_1, q_2, ..., q_n) ) in n-dimensional space is calculated as:
$$d(P, Q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$$
This measures the straight-line distance between two points in the coordinate space.
Tie-Breaking Policy: When multiple points have identical distances to the query point, the tie is resolved by preserving the original input order—the point that appears earlier in the input list takes precedence over one that appears later.
Your Task: Write a Python function that retrieves the k nearest neighbors from a collection of points. The function should:
points = [[1, 2], [3, 4], [1, 1], [5, 6], [2, 3]]
query_point = [2, 2]
k = 3[[1, 2], [2, 3], [1, 1]]Computing Euclidean distances from query point (2, 2) to each point:
• Point [1, 2]: √((2-1)² + (2-2)²) = √1 = 1.0 • Point [3, 4]: √((2-3)² + (2-4)²) = √5 ≈ 2.24 • Point [1, 1]: √((2-1)² + (2-1)²) = √2 ≈ 1.41 • Point [5, 6]: √((2-5)² + (2-6)²) = √25 = 5.0 • Point [2, 3]: √((2-2)² + (2-3)²) = √1 = 1.0
The 3 smallest distances are 1.0 ([1, 2]), 1.0 ([2, 3]), and 1.41 ([1, 1]). Since [1, 2] and [2, 3] have identical distances, [1, 2] appears first because it has a lower input index.
points = [[0, 0], [1, 0], [0, 1], [1, 1], [2, 2]]
query_point = [0, 0]
k = 2[[0, 0], [1, 0]]Computing Euclidean distances from query point (0, 0):
• Point [0, 0]: √0 = 0.0 (exact match) • Point [1, 0]: √1 = 1.0 • Point [0, 1]: √1 = 1.0 • Point [1, 1]: √2 ≈ 1.41 • Point [2, 2]: √8 ≈ 2.83
The 2 nearest points are [0, 0] with distance 0.0 and [1, 0] with distance 1.0. Note that [1, 0] and [0, 1] have equal distances, but [1, 0] is selected because it appears earlier in the input.
points = [[1, 1, 1], [2, 2, 2], [3, 3, 3], [0, 0, 0], [1, 0, 1]]
query_point = [1, 1, 1]
k = 2[[1, 1, 1], [1, 0, 1]]This example demonstrates 3-dimensional space. Computing distances from query point (1, 1, 1):
• Point [1, 1, 1]: √0 = 0.0 (exact match) • Point [2, 2, 2]: √((1-2)² + (1-2)² + (1-2)²) = √3 ≈ 1.73 • Point [3, 3, 3]: √((1-3)² + (1-3)² + (1-3)²) = √12 ≈ 3.46 • Point [0, 0, 0]: √((1-0)² + (1-0)² + (1-0)²) = √3 ≈ 1.73 • Point [1, 0, 1]: √((1-1)² + (1-0)² + (1-1)²) = √1 = 1.0
The 2 nearest points are [1, 1, 1] (distance 0.0) and [1, 0, 1] (distance 1.0).
Constraints