Disjoint Placement Probability of Line Segments via Geometry

Abstract

We have shown that when any finite number n, of line segments with total combined length less than one, have their centers placed randomly inside the unit interval $[0,1]$, the probability of obtaining a mutually disjoint placement of the segments within $[0,1]$, is given by the expression ${(1-L)}^n$ where $L=\left|L_1\right|+\cdots +\left|L_n\right|$, and $\left|L_k\right|$ denotes the length of the k-th segment, L_k. The result is established by a careful analysis of the geometry of the event, “all segments disjoint and contained within [0,1],” considered as a subset of the uniform probability space of n centers, each of which is in $[0,1]$; that is to say, the unit n-cube of ${\mathbb{R}}^n$. This event has an interesting geometric structure consisting of $n!$ disjoint, congruent, (up to a mirror image) polytopes within the unit n-cube. It is shown these event polytopes fit together perfectly to form, except for a set of measure zero, a partition of an n-dimensional cube with common edge length $1-L$, and hence an n-volume given by the formula. In the case of n = 3 segments, the polytopes form one of the known tetrahedral partitions of the cube as discussed, for example in [4]. In fact for all n > 0, the polytopes comprise a partition of the n-dimensional hypercube, and are therefore n-dimensional space filling.

Acknowledgment

The authors are grateful to Barry Cipra and Paul Zorn, along with the other members of the “Northfield Math Mafia,” for their insightful comments. We thank the referee for several suggestions that improved the readability of the paper.

Notes

1 A shape is placed at random, then tested for intersection with any previously placed shapes and the boundary. If no intersections are found, the process repeats with the next smaller shape. If intersections are found, that placement is discarded and the algorithm tries again until a either a disjoint placement is found, or until some prespecified number of attempts have been made, at which point the algorithm is said to have jammed.

2 More generally we could take the containing region to be any interval of length I, and any finite number of line segments whose total combined length is less than I. In this article we stick with I = 1.

3 Uniform meaning all placements are equally likely.

4 By polytope we mean an n-dimensional region of ${\mathbb{R}}^n$ bounded by (n-1)-dimensional hyperplanes.

5 Note the “permuted”order of the inequalities; the first giving conditions on $x_{j_n}$; the second giving conditions on $x_{j_{n-1}}$, and so on.

6 The total lengths of the line segments used for Figure 2 are $\ll 1$, so that the probability of mutually disjoint placement is quite large, accounting for the large volume shown within the unit 3-cube

7 The strict inequalities imply vertices, edges and faces are not contained in the polytopes themselves. That is, the polytopes are open sets. Nevertheless, we speak of the “maximum” or “minimum” value for a segment center, when what we actually mean is the left or right endpoint of its allowable range.

8 Proposition 1, again!

9 There being both a right hand and a left hand version, as with a pair of shoes.

10 The polytopes are congruent, as suggested by Figure 2, (up to mirror image), as can be seen intuitively from the algebraically similar form of their defining inequalities given in 7. The isometries of ${\mathbb{R}}^n$ turn out to be compositions of a coordinate permutation function with a translation specific to the given pair of polytopes. The isometries will be either orientation preserving or reversing, depending on the coordinate permutation employed.

11 Further, there would seem to be an additional assumption needed in higher dimensions, beyond requiring the combined areas of the shapes be less than the area of the containing region. Namely, that there is at least one disjoint configuration of the shapes that fits into the containing region. With line segments this latter condition is a consequence of the former, but that is not the case in two or more dimensions!

Additional information

Notes on contributors

Christopher Ennis

Christopher Ennis ([email protected]) attended UCLA and UC Berkeley. After holding several academic appointments, he settled into a rewarding 24 year teaching career at Normandale Community College, including several years as department chairperson. Retiring in 2016, he has again found time to do mathematical research.

John Shier

John Shier ([email protected]) has physics degrees from Caltech and the University of Illinois. He was an adjunct instructor of physics at Normandale Community College, Bloomington MN from 2001 to 2008. He has been retired since that time.