Intersecting rectangles.

[Anglister, Shlomo]

Hi,
Consider the following algorithms:

1) Generate a random rectangular cover of the plane.
2) Shift all rectangles at random until you satisfy the clique
condition.
   This is a naive approach with bad complexity that will do the job.

1) Generate flowers (cliques) built from rectangles with the desired
clique size.
2) Spread them in the plane.

Hope it helps.
Shlomo

-----Original Message-----
From: Rajiv Raman [mailto:rraman at cs.uiowa.edu] 
Sent: Wednesday, December 10, 2003 6:01 AM
To: compgeom-discuss at research.bell-labs.com
Subject: Intersecting rectangles.



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.

-------------
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.