Intersecting rectangles.

[Rajiv Raman]

Hi,

I'm experimenting with some coloring algorithms for intersection graphs of
(isothetic) rectangles (primarily in the plane, but want to experiment
with these techniques for higher dimensional rectangles also).

In this context, rectangles are said to intersect only if the area of
intersection is non-zero.

In order to test these algorithms, I want to write a program that would
take as parameters, (n,k), where n is the number of rectangles, and k is
the maximum number of rectangles that share a point in their interior.
(And hence, the corresponding graph has a clique of size atmost k). The
program would generate n rectangles at random with the desired 
intersection property.

I was wondering if there were known efficient algorithms/data-structures
for this problem, or what would be a simple way to implement this.

All techniques I could think of involved generating a random rectangle,
and then testing if it satisifies the intersection constraint. If it
doesn't, then I throw the rectangle away and generate another, and
continue till I have generated n rectangles.

However, this doesn't seem to work well for large values of n and small
values of k.

I would be grateful if anyone could provide pointers in this regard.

Thanks, 
Rajiv





-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.