Packing random rectangles |
| |
| Authors: | EG Coffman Jr George S Lueker Joel Spencer Peter M Winkler |
| |
| Institution: | (1) Electrical Engineering Department, Columbia University, New York, NY 10027, USA., US;(2) Information and Computer Science Department, University of California, Irvine, CA 92697-3425, USA. e-mail: lueker@ics.uci.edu, US;(3) Mathematics Department, New York University, New York, NY 10003, USA, US;(4) Bell Labs, Lucent Technologies, 700 Mountain Avenue, Murray Hill, NJ 07974, USA, US |
| |
| Abstract: | A random rectangle is the product of two independent random intervals, each being the interval between two random points
drawn independently and uniformly from 0,1]. We prove that te number C
n
of items in a maximum cardinality disjoint subset of n random rectangles satisfies
where K is an absolute constant. Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we are able to show that, for some absolute constat K,
Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Q
n
of items in a maximum cardinality disjoint subset of the cubes satisies
Received: 1 September 1999 / Revised version: 3 November 2000 / Published online: 14 June 2001 |
| |
| Keywords: | Mathematics Subject Classification (2000): Primary 52C17 Secondary 05C69 52C15 60D05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
