MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Number of interval Intersections for a large number of

On Oct 2, 2:43 am, P_ter <peter_van_summe... at> wrote:
> It seems I was not clear enough in my problem.
> I have a few thousand intervals {e1,e2,...} each of which is like {begin,end}
> The elements e are ordered according to their begin value.
> Some intervals do not intersect. But it also can be like this (the points are only for making a clear drawing):
> .......<------>
> ...<------------------->
> <------------------>
> So, in this case the first interval can be partioned :
>       in a part which has no intersection with the other two,
>       in a part which intersects twice,
>       in a part which intersects three times,
>       in a part which intersects two times.
> For each interval I make a Block[x] = UnitStep[x-beginvalue]-UnitStep[x-endvalue]
> I sum all the Blocks to one function and ask Reduce to find me a solution for those parts of intervals which intersects only three times: Reduce[SumOfBlocks[x]==3,x].
> Because it is a sum of UnitSteps and where there are three times an intersection, the value is 3.
> And so on for 1,2,4,5,etc.
> It is a safe way to do it, but not so fast. Are there other algorithms? Where can I find them?

Here's a slightly simpler way to do it.

Generate some intervals.

t = Sort[Sort/@Table[Random[],{n = 10},{2}]]*(max = 100)



Get the overlaps.

{p,q} = {Partition[ Join[{0},#[[All,1]],{max}], 2, 1],
          FoldList[ Plus, 0, #[[All,2]]]}& @
        Sort@Flatten[Transpose@{#,{1,-1}}&/@t, 1]
r = {#,Pick[p,q,#]}& /@ Range[0,Max@q]




If you don't want all of r at once, Pick[p,q,x] will give
a list of the intervals whose overlap depth is x.

  • Prev by Date: Re: Re: Tooltips in ContourPlot
  • Next by Date: Re: Re: Equivalent functionality to colorbar in Mathematica?
  • Previous by thread: Re: Number of interval Intersections for a large number of
  • Next by thread: Re: Creating "sticky" item in File >> Open Recent menu?