Affordable Access

An Existential Proof of the Conjecture on Packing Anchored Rectangles

Authors
  • Banerjee, Sandip
  • Banik, Aritra
  • Bhattacharya, Bhargab B.
  • Bishnu, Arijit
  • Chatterjee, Soumyottam
Type
Preprint
Publication Date
Apr 28, 2014
Submission Date
Oct 31, 2013
Identifiers
arXiv ID: 1310.8403
Source
arXiv
License
Yellow
External links

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.

Report this publication

Statistics

Seen <100 times