Return to Question

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).

UPDATE: I cited this thread in the following working paper. I hope it will be accepted.

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).

UPDATE: I cited this thread in the following working paper. I hope it will be accepted.

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).

UPDATE: I cited this thread in the following working paper. I hope it will be accepted.

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:

The following C-shape has a maximum anti-rectangle with 3 squares:

And the following shape has a maximum anti-rectangle with 5 squares:

When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:

For every $C$, there is a maximum anti-rectangle, which contains a corner square.

(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).

I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).

Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?

CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).