Average-case analysis of rectangle packings

E. G. Coffman, George S. Lueker, Joel Spencer, Peter M. Winkler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 θ(n1/2). Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we have been able to show that ω(n1/2) and O((n logd-1 n)1/2) are asymptotic lower and upper bounds. In addition, we can prove that θ(nd/(d+1)) is a tight asymptotic bound for the case of random cubes.

Original languageEnglish (US)
Title of host publicationLATIN 2000
Subtitle of host publicationTheoretical Informatics - 4th Latin American Symposium, Proceedings
Pages292-297
Number of pages6
DOIs
StatePublished - 2000
Event4th Latin American Symposium on Theoretical Informatics, LATIN 2000 - Punta del Este, Uruguay
Duration: Apr 10 2000Apr 14 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1776 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th Latin American Symposium on Theoretical Informatics, LATIN 2000
CountryUruguay
CityPunta del Este
Period4/10/004/14/00

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Average-case analysis of rectangle packings'. Together they form a unique fingerprint.

Cite this