Problem: Is it a rectangle?

[Raphael Clifford <raph@dcs.kcl.ac.uk>]

Hi,

Given a set of (d dimensional hyper-) rectangles (which may overlap) 
with integer coordinates I have the following problem:

1) Add one rectangle at a time from the set
2) Output Yes whenever the union of the (possibly overlapping) 
rectangles added forms a rectangle itself.  Output No otherwise.

d may be as large as 10.  Is there an efficient solution to this?   
Ideally an online solution is preferable so that the whole algorithm 
doesn't have to be rerun for each rectangle added.

The only literature I can find seems to concentrate on giving the area 
of the union (Klee's measure problem). However I do not need that much 
information except for the very rare case where the union is rectangular 
itself and then the area is trivial to compute. The rectangles have 
edges orthogonal to the axes.

Kind regards,
Raphael




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