cluster analysis - What algorithm could be used to fast clustering point in polyline shape? -

suppose have line consisting of 2dpoints enter image description here

what algorithm efficiently compute clusters in line given input of active points?

red here points. yellow - active points in given time.

in example algorithm should find 2 clusters (blue).

you following:

cluster points index. can done in linear time. save cluster's bounding box in process
for each pair of clusters
- check if bounding boxes intersect or have maximum distance t
- if so, check if there 2 points both clusters have maximum distance of t
- if so, merge clusters

t distance threshold. can either static or based on cluster (e.g. maximum distance nearest neighbour of cluster's point).

this algorithm has still quadratic time complexity, should fast enough due pre-clustering , bounding box test.

Cap