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?