Random placement of non-overlapping intervals

10
votes

I have an interval G, and a set of non-overlapping sub-intervals of various lengths s1, s2, ..., sn.

G |--------------------------------------------------------------// //-----------|
        s1 [---]                       s3 [------------------]
                    s2 [------]                                         sn [--]

I'm looking for an algorithm for taking all of these sub-intervals and then placing them again on G randomly, such that they don't overlap. What is the best way to do this?

The easiest, most naive approach would be simply to randomly select starting positions for each subinterval, check for overlaps once all intervals are placed, and then start over if there are overlaps. This would probably be pretty fast if the sub-intervals provide sparse coverage of G, but increasingly inefficient as density increases.

A similar idea is to check for overlap as each sub-interval is placed. Similar concerns about efficiency though.

Is there any more clever way of handling this?

UPDATE

To clarify a couple of points:

  • It is the spacing of the sub-intervals that I would like randomly distributed.
  • The uniform distribution is probably the most appropriate concept of randomness in this case.
  • These are discrete (integer) closed intervals, not continuous.
2
algorithmrandomintervals
I think you need to specify (1) what distribution you want, and (2) what exactly you want to be randomly distributed. The left sides of the sub-intervals, the right sides (as measured from the left), the gaps in between them? Once you specify them you can test for it formally. – user1666959
Excellent question: it is the spacing of the sub-intervals (and accordingly the gaps between them) that I would like randomly (probably uniformly) distributed. – Daniel Standage
I'm stil missing something: the sum of the length of sub intervals is a number S. G-S is then the sum of all spaces. So you want N+1 random numbers (N-1 would separate the N intervals and you want one more on each end) drawn from the uniform distribution such that their sum is G-S. Right? Nice question. Would you mind telling where does it arise? – user1666959

2 Answers

9
votes

I think okio's answer will give a biased distribution of the gaps (i.e. the first gaps will tend to be larger then later gaps.

However, I think a very similar approach should work better:

  1. Shrink all sn to zero length
  2. Choose random positions for each sn in lenG-lenS
  3. Expand sn back to their original lengths
4
votes

Something like this ?

lenG = length(G)
lenS = length(s1) + length(s2) + length(s3) + length(sn)

empty_place_available = lenG - lenS
current_position = 0;

sort sn randomly

loop for each sn
    rand = rand(0, empty_place_available)
    position[sn] = current_position + rand
    empty_place_available = empty_place_available - rand
    current_position = current_position + rand + length(sn)