An Existential Proof of the Conjecture on Packing Anchored Rectangles

MaRDI QIDQ6246057zbMATH OpenFDO

Authors Sandip Banerjee, Aritra Banik, Bhargab B. Bhattacharya, Arijit Bishnu, Soumyottam Chatterjee

Publication date 31 October 2013

Abstract: Let $P_n$ be a set of $n$ points, including the origin, in the unit square $U=[0,1{]}^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_n$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.

This page was built for publication: An Existential Proof of the Conjecture on Packing Anchored Rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6246057)