# Data Structure to join points by similarity measure

I have a series of points `(x,y)` and each point has a colour (in the LAB colour space). I need to associate points by similar colour and then spatially. So the end result is each point becomes part of a local cluster or segment.

Is there a specific data structure that is suited to such a scenario? I'm trying to find a data structure that can efficiently find the n surrounding points of a specific point.

Essentially I need to select point `P` and find the surrounding points. For each surrounding point (`Q`); measure the Euclidean colour distance between `P` and `Q`, if the distance is within a threshold, these points get the same label. Then repeat for point `Q` until `Q` is surrounded by points of its own label or points that are too dissimilar to accumulate.

I'm aware of machine learning algorithms that could achieve what I want; SVM (Support Vector Machines) however it is not quite fast enough. If there is a data structure that can perform this faster its more desirable.

## 1 Answer

You seem to be describing a linkage-based hierarchical clustering algorithm. However, you have an unusual metric: Two points don't have a scalar distance, but a separate coordinate-distance and color-distance. This may or may nor be a problem.

The act of finding all elements within a given distance is a range search or range query. This requires a concept of distance/metric. You may therefore have to perform range searches based on the coordinate-metric first and filter the result set to account for your color-metric. While this approach is not generally possible, it works fine here because the color-distance component strictly increases total distance.

Even absent any metric, k-d trees can be used to organize multi-dimensional data. A k-d tree is a binary tree that partitions on a different dimension for each level. This allows somewhat efficient range queries because we can skip sub-trees if all their elements must be out of range, given the metric. The search space is effectively delimited by a hypercube rather than a hypersphere defined by the query's range. There are more efficient spatial data structures such as ball trees, but k-d trees are easy to implement.

While tree based data structures have attractive algorithmic complexities, these don't necessarily matter. For smaller data sets, a flat array of coordinates that you scan linearly might have better performance due to cache effects. If the coordinates are on a densely populated grid (e.g. because you are processing a bitmap) then you can get rid of explicit coordinates as you can easily calculate the offsets of all neighbors.