# How to calculate number of lumps of a 1D discrete point distribution?

I would like to calculate the number of lumps of a given set of points.

Defining "number of lumps" as "the number of groups with points at distance 1"

Supose we have a discrete 1D space in this segment For example N=15

    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15


Then we have a set of M "marks" distributed, For example M=8

Distributed all left:

    x  x  x  x  x  x  x  x  .  .  .  .  .  .  .
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15


Groups with points at minimal distance = 1 (minimum)

Distributed divided by two:

    x  x  x  x  .  .  .  .  .  .  .  x  x  x  x
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15


Groups with points at minimal distance = 2

Equi-distributed :

    x  .  x  .  x  .  x  .  x  .  x  .  x  .  x
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15


Groups with points at minimal distance = 8 (maximum) (perhaps other answer here could be "zero lumps" ?)

Other distribution, etc:

    x  x  .  .  x  x  .  .  x  x  .  .  x  x  .
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15


Groups with points at minimal distance = 4

It's quite obvious algorithmically, just walking the segment, and count every "rising edge", number of times it passes from empty to a point.

But I would like to solve it more "mathematically", to think the problem in an abstract way, having a 1D math solution perhaps would help to scale the concept to higher dimentions, where distance is complex ("walking the segment" trick won't work anymore), (not to mention a discrete metric space)..

How can I put that into an equation, a weighted sum or something like that?

Thanks for any help

-

## 1 Answer

If you are looking for a general formula that, given the points, returns the number of clusters (I think that "cluster" is a more common name that "lump", in this context), I'm afraid you won't find it. The problem is quite complicated, and there are many algorithms (google for hierachical clustering, percolation). For you particular case (discrete grid, and a threshold distance from nearest neighbours as criterion for clusters) this Hoshen-Kopelman Algorithm seems appropiate.

-
I think this equation does the "algorithm" where f(k) = "1"(one) if there is a mark and "0"(zero) if empty: $nclusters = \sum_{k=0}^{N-1} {f(k)*(1-f(k-1))}$ , with $f(-1)=0$ and you are right perhaps this get complicated for other "distance" definitions, but for the moment I am fine with 1D :) – Hernán Eche Aug 24 '11 at 4:59
I though you were insterested in solutions that generalize to n-dimensions. In 1D it's easy to get a formula, because it's just a matter of counting "transitions", but that does not ease the actual computation, nor does generalize to higher dimensions, as far as i see. – leonbloy Aug 24 '11 at 11:22
yes, I am interested in higher dimensions, but as the math I pursuit is numerable, mappable to the integers, and as there are some higher dimensions spaces that are mappable to integers, perhaps it's ok, one dimension at a time, for the math I need, things as Real numbers are Unreal – Hernán Eche Aug 24 '11 at 22:02