Clusters on a map of epicentres
A seismologist has marked earthquake epicentres on a map and wants to split them into groups the way DBSCAN does: dense clusters are clusters, lone shocks are noise.
Given n points of the plane, a radius ε and a threshold minPts. The neighbours of a point are all points at a distance of at most ε from it, including itself (points with the same coordinates are different points and neighbours of each other). A point is a core if it has at least minPts neighbours. Two cores that are neighbours lie in one cluster, and so on along a chain: a cluster is cores linked by chains of neighbouring cores. A point that is not a core but is a neighbour of at least one core is a border point. All other points are noise.
Print the number of clusters, cores, border points and noise points.
Tests three to five are real epicentres of earthquakes of magnitude 5 and above from the USGS catalogue: an arc of islands in the north-west Pacific for 2018–2021 and for all of 2015–2025, then the south-west Pacific for 2015–2025. Coordinates are kilometres on a flat map of the region; distances from its middle on the map are the same as along the Earth's surface.
Input
The first line holds n, ε and minPts (1 ≤ n ≤ 10⁵, 0 ≤ ε ≤ 10⁶, 1 ≤ minPts ≤ n). Then n lines with integer coordinates x, y (at most 10⁶ in absolute value). It is guaranteed that there are at most 5·10⁵ pairs of points at a distance of at most ε.
Output
Four numbers separated by spaces: clusters, cores, border points, noise.
Examples
Example 1
9 2 3 0 0 1 1 2 0 1 -1 4 0 10 10 11 10 12 10 20 0
2 7 1 1
Example 2
10 2 4 0 0 0 1 -1 0 -1 1 2 0 4 0 4 1 5 0 5 1 2 5
2 8 1 1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 14 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Comparing every point with every other is 5·10⁹ distances for 10⁵ points. But by the statement there are few neighbours: how can you avoid looking at points that are certainly far away?
2Hint 2
Cut the plane into squares with side ε. Where can a point's neighbours lie if its square is known?
3Hint 3
The answer does not depend on the order in which the points are traversed: cores are determined by the number of neighbours, and clusters are connected groups of cores. Which data structure glues groups together?
4The idea
A point's neighbour is at most ε away from it in each coordinate, so it lies in the point's grid square or in one of the eight adjacent ones. Put the points into squares in a dictionary and for each point check only these nine squares. Having counted the neighbours, we know the cores; clusters are the connected components of the graph “core – neighbouring core”, and they are conveniently gathered with a disjoint set union (DSU). A border point is a non-core that has a core among its neighbours.
5Walkthrough
The key of a square is the pair (⌊x/ε⌋, ⌊y/ε⌋). It must be rounded down: in Python that is //, while in Go the operator / rounds towards zero, and the square around zero comes out twice as wide as the others. The answer does not suffer from this, since neighbours still end up in adjacent squares, but there are more points to compare; it is cleaner to write division with rounding down.
A separate case is ε = 0: you cannot divide by zero, and the neighbours are only points with the same coordinates. It is enough to take max(ε, 1) as the side of a square.
It is handy to go by squares rather than by points: for a square, collect once the points of the nine squares around it and compare each of its own points with them. The neighbour lists found are kept whole: by the statement their total length is at most n + 10⁶. Then three passes: cores (list length ≥ minPts), uniting each core with its neighbouring cores in the DSU, then counting roots among the cores and border points among the rest.
On the first real test, 185 earthquakes of 2018–2021 along an arc of islands in the north-west Pacific with ε = 100 km and minPts = 4, the result is 6 clusters, 167 cores, 6 border points and 12 noise points: the same numbers as in the article's step-by-step scene.
5+Solution
6Complexity
O(n + C) time, where C is the number of comparisons with the points of nine adjacent squares. When the points are distributed without degenerate clumps, C is a small multiple of the number of neighbouring pairs. Memory O(n + number of neighbouring pairs).
Note that the grid does not make the problem linear in the worst case. If all the points lie in two adjacent squares but further than ε from each other, there are again about n² comparisons. The tests have no such clumps; the general case is in the article, in the section on cost.
7Common mistakes
- Scanning all pairs. The answer is right, but on 10⁵ points the time limit is exceeded.
- Not counting the point itself. By the statement a point is its own neighbour; without it there are fewer cores, and the answer differs in almost all tests.
- Gluing clusters through border points. If a core is united with all its neighbours rather than only with cores, a border point between two clusters merges them into one. The second sample catches this: two groups of four cores and one point in between.
- Division by zero with ε = 0: the side of a square must be at least 1.
- A border point counted twice, if it neighbours cores of two clusters. Border points are counted by points, not by “border point – cluster” pairs.