ISSN:
1432-2064
Keywords:
60D05
;
05B40
;
52A22
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Summary Letn random intervalsI 1, ...,I n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this “best” packing has wasted space $$O(\frac{{\log ^2 n}}{n})$$ . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01295224
Permalink
