MathDB

In the cartesian plane consider rectangles with sides parallel to the coordinate axes. We say that one rectangle is below another rectangle if there is a line

g

parallel to the

x

-axis such that the first rectangle is below

g

, the second one above

g

and both rectangles do not touch

g

.
Similarly, we say that one rectangle is to the right of another rectangle if there is a line

h

parallel to the

y

-axis such that the first rectangle is to the right of

h

, the second one to the left of

h

and both rectangles do not touch

h

.
Show that any finite set of

n

pairwise disjoint rectangles with sides parallel to the coordinate axes can be enumerated as a sequence

(R_1,\dots,R_n)

so that for all indices

i,j

with

1 \le i<j \le n

the rectangle

R_i

is to the right of or below the rectangle

R_j

Problem Statement