# 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 don't see the problem with the "algorithmic" solution. If the space consists of $n$ points, then this solution runs in $n$ time. This is also of course the minimum time needed, since you have to check each point to see if it is occupied or not. Any "mathematical" solution would be at most as efficient as this solution. –  TMM Aug 23 '11 at 23:52
Ah, my apologies, I misunderstood the question. leonbloy's answer may be what you were looking for. –  TMM Aug 24 '11 at 1:04
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