I'm working on an algorithm for orthogonal line intersection detection and am trying to analyze some things about it. For simplicity, we can consider the problem as follows:
Given N randomly generated intervals with unique start and end points (ranging from 0 to 2N), I would like to find:
- What is the average length of each interval?
My initial figuring seems like the average length is N/2 for the following reason: The start of an interval S1 is within [0, 2N-1], making the mean ~N. If the start is N, the end must fall within [N+1, 2N-1], making the mean ~(3N)/2, giving it a length of N/2.
- What is the probability that two intervals will overlap?
If from above, we say the length of the segments |S1| = |S2| = N/2. If S1 runs from [0, N/2], then S2 must start after N/2. Since |S2| = N/2, it can only start from N/2+1 to 3N/2, making the probability of overlap 1/3. If S1 is [N/2, N], then S2 must start after N, making the probability of overlap 2/3. By symmetry, the same follows as we further increase the starting point of S1, making the overall probability of overlap 1/2.
- If those overlapping intervals make up a new interval, what is the probability that it will overlap with another 'merged' interval?
This seems way more complex and would depend on the length of the two merged intervals. No clue how to work this one out.
- Finally, if we continue picking pairs of intervals and either merging them if they overlap or forming them into a two-interval set if they don't overlap, what is the average number of intervals I will have in my final set after log(N) steps?
This is really the end-goal of the my analysis of this algorithm. The algorithm involves creating a binary tree and merging segments at each level, and I want to see how much average space will be required.
Sorry for such a convoluted problem, but any help would be greatly appreciated! Thanks!
