Re: Number of interval Intersections for a large number of
- To: mathgroup at smc.vnet.net
- Subject: [mg81711] Re: Number of interval Intersections for a large number of
- From: P_ter <peter_van_summeren at yahoo.co.uk>
- Date: Tue, 2 Oct 2007 05:32:28 -0400 (EDT)
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?