| Autor: |
Gonnet, Gastón H., Panario, Daniel, Viola, Alfredo, Coffman, E. G., Lueker, George S., Spencer, Joel, Winkler, Peter M. |
| Zdroj: |
LATIN 2000: Theoretical Informatics; 2000, p292-297, 6p |
| Abstrakt: |
We study the average-case behavior of algorithms for finding a maximal disjoint subset of a given set of rectangles. In the probability model, a random rectangle is the product of two independent random intervals, each being the interval between two points drawn uniformly at random from [0, 1]. We have proved that the expected cardinality of a maximal disjoint subset of n random rectangles has the tight asymptotic bound Θ (n 1/2). Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we have been able to show that Ω (n 1/2) and O ((n logd − 1n)1/2) are asymptotic lower and upper bounds. In addition, we can prove that Θ (n d/(d + 1)) is a tight asymptotic bound for the case of random cubes. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
