# 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

-

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