Problem: Is it a rectangle?
raph at dcs.kcl.ac.uk
Sun Aug 1 18:23:44 PDT 2004
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.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce