DBSCAN Core Points

Identify core points in the DBSCAN algorithm.

A point is a core point if it has at least min_pts neighbors (including itself) within distance epsilon.

Given data points, epsilon, and min_pts, return the indices of all core points (sorted).

Use Euclidean distance for proximity.

Example

Input

X = [[0, 0], [1, 0], [0, 1], [10, 10]]
epsilon = 1.5
min_pts = 3

Output

[0, 1, 2]

Reasoning

X holds 4 points in the plane, indexed 0 to 3. epsilon = 1.5 is the neighbourhood radius and min_pts = 3 is the neighbourhood size needed, the point itself included.
Distances among the first three points: $d(0,1) = 1$ , $d(0,2) = 1$ and $d(1,2) = \sqrt{1^2 + 1^2} = \sqrt{2} \approx 1.414$ . All three are at most 1.5.
So point 0's neighbourhood is $\{0, 1, 2\}$ , size 3, and the same set works for points 1 and 2. Each meets the threshold of 3 exactly, so all three are core points.
Point 3 at $(10, 10)$ is far from everything: $\sqrt{10^2 + 10^2} \approx 14.14$ to point 0 and $\sqrt{9^2 + 10^2} \approx 13.45$ to points 1 and 2. Its neighbourhood is just $\{3\}$ , size 1 < 3.
The output [0, 1, 2] lists core indices in increasing order. Notice the tight margin: with epsilon = 1.4 points 1 and 2 would each see only 2 neighbours and only point 0 would remain core.

Constraints

X: 2D list of data points
epsilon: maximum distance for neighborhood
min_pts: minimum number of points in neighborhood (including self)
Return sorted list of core point indices

Learn this in

ClusteringML Study Plan

More from Machine Learning 2

Kernel PCAhard PCA via Covariance Matrixmedium Variance Explained Ratioeasy Feature Scalingeasy GAN Discriminator Losshard

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results