0
$\begingroup$

I am trying to prove the following (if it is true or false, I am not sure but I want to prove in either case.)

Let R be the set of all rectangles with a center point c and area a and r belongs to R. Assuming that all rectangles are equally likely, the expected area of overlap between R and r is maximized when r is a square.

(All rectangles and the square is constructed from same center and have same area a as given. All rectangle are axis parallel. With equally likely, it is meant that if there is rectangle r along x axis, then we can flip this rectangle by 90 degree to get another rectangle. So if one rectangle occurs, the flip version of the same rectangle also occurs.)

Thanks

$\endgroup$
  • $\begingroup$ As far as proving it goes, it'd be simpler with a finite collection of rectangles (that still satisfy "symmetry" in their ratio) or restrict the range of the admissible ratio. Strictly speaking in such infinite collection you should specify the pdf function, since we can't make it uniform when every ratio is possible. And dealing with a general pdf that only satisfy the property you describe makes the proof a tad more annoying. But the result is most likely true. $\endgroup$ – N.Bach Jun 3 '17 at 13:27
  • $\begingroup$ It is unclear to me what "area of overlap" actually means. If rectangle $A$ overlaps rectangle $B$, giving overlap area $b$, and $A$ overlaps $C$, giving overlap area $c$, is the "area of overlap" (1) the sum $b + c$ or (2) the area that the two overlaps have in common or (3) the sum minus the area they have in common? $\endgroup$ – Jens Jun 3 '17 at 21:47
  • $\begingroup$ Also, are you considering only a subset of $R$? Because if all possible rectangles are included, the area of overlap for any rectangle in the three cases I gave above would be (1) infinite (2) 0 and (3) a. $\endgroup$ – Jens Jun 3 '17 at 22:01
  • $\begingroup$ @Jens We're looking at the expected overlap area, assuming you only have the two rectangles $B$ and $C$, the value to maximise is the mean between $b$ and $c$, so $(b+c)/2$. $\endgroup$ – N.Bach Jun 3 '17 at 22:08
0
$\begingroup$

Tl;dr : the property is in general false, but for the suggested distribution it is true.

Parameterization of the family

For a rectangle of $x$-width $w$ and $y$-height $h$, let's denote its aspect ratio by $\rho=\frac wh$. Rectangles $r\in R$ are fully defined by their ratio $\rho$, $$ R=\left\{\text{rectangle of ratio $\rho$} \mid h=\sqrt{\frac A\rho},\ w=\rho h \right\} $$ Given some rectangle in $R$ of ratio $\rho_0$, its overlap with another rectangle of $R$ with ratio $\rho$ is $f(\rho,\rho_0)=\min\{ w;\ w_0\}\times\min\{ h;\ h_0\}$. Assuming that $\rho\le \rho_0$ and using the above formula we end up with $f(\rho\le\rho_0)=A\sqrt{\frac\rho{\rho_0}}$. In the other case we have $f(\rho\ge\rho_0)=A\sqrt{\frac{\rho_0}\rho}$.

The pdf

From your description of the mean you want, you have some pdf function on $\rho$ that satisfies something like $\forall 1\le \rho_1\le\rho_2$, $$ \int_{\rho_1}^{\rho_2}\operatorname{pdf}(\rho)\,d\rho= \int_{1/\rho_2}^{1/\rho_1}\operatorname{pdf}(\rho)\,d\rho $$ If you perform the change of variable $X=\frac 1\rho$ on the right hand side you get $$ \int_{\rho_1}^{\rho_2}\operatorname{pdf}(\rho)\,d\rho= \int_{\rho_2}^{\rho_1}\operatorname{pdf}\left(\frac 1X\right)\,\frac{-dX}{X^2}= \int_{\rho_1}^{\rho_2}\frac{\operatorname{pdf}\left(\frac 1X\right)}{X^2}\,dX $$ so you have $\rho^2\operatorname{pdf}(\rho)=\operatorname{pdf}(1/\rho)$. If you specify the pdf for $\rho$ values greater than $1$, it is fully specified (and conversely if you give the pdf for $\rho\le 1$).

For short, whenever taking the inverse would be interesting in an integration we have $$ \int_{\rho_1}^{\rho_2} f(\rho)\operatorname{pdf}(\rho)\,d\rho= \int_{1/\rho_2}^{1/\rho_1} f\left(\frac 1\rho\right)\operatorname{pdf}(\rho)\,d\rho $$

Uniform(?) distribution on bounded interval

Assuming you restrict the range of admissible ratio, so we can have a pseudo uniform distribution. Let $\rho_\text{max}$ be the maximum ratio. For $\rho>\rho_\text{max}$ we have $\operatorname{pdf}(\rho)=0$, which also implies that for $\rho< 1/\rho_\text{max}$, $\operatorname{pdf}(\rho)=0$.

Consider the top right corner of a rectangle. As its ratio goes from $1/\rho_\text{max}$ to $\rho_\text{max}$, this corner traces a portion of a hyperbola. The "uniform distribution" that matches what you want to do, as far as I understand, is that any point on that hyperbola is equally likely to yield a rectangle in the family. This unfortunately does not result in a uniform distribution in the ratio/width/height, but a uniform distribution in the curvilinear abscissa $$ s(\rho)=\frac {\sqrt{A}}2 \int_{1/\rho_\text{max}}^\rho \sqrt{\frac{1+u^2}{u^3}}\,du $$ To get this expression, note that the hyperbola can be parameterised in $\rho$ as the set of points $\left\{ \left(\sqrt{\rho A},\ \sqrt{\frac A\rho}\right) \right\}$, the tangent vector is then $ \mathbf N(\rho)=\sqrt{A}\left( \frac 1{2\sqrt\rho},\ \frac{-1}{2\rho\sqrt\rho} \right) $ and by definition $ ds = \left\| \mathbf N(\rho) \right\|\,d\rho =\frac{\sqrt A}2\sqrt{\frac{1+\rho^2}{\rho^3}}\,d\rho $.

Consider a specific rectangle with ratio $\rho_0$ in the range $1/\rho_\text{max}$ and $\rho_\text{max}$.

\begin{align*} \mathbb E[\operatorname{overlap}] &=\int_{s=0}^{s_\text{max}} \frac{f(s,s_0)}{s_\text{max}} \,ds\\ &=\int_{1/\rho_\text{max}}^{\rho_\text{max}} \frac{f(\rho,\rho_0)}{s_\text{max}}\times \frac{\sqrt{A}}2 \sqrt{\frac{1+\rho^2}{\rho^3}}\,d\rho\\ \frac{2s_\text{max}}{\sqrt A}\mathbb E[\operatorname{overlap}] &=\int_{1/\rho_\text{max}}^{\rho_0}A\sqrt{\frac{\rho}{\rho_0}} \sqrt{\frac{1+\rho^2}{\rho^3}}\,d\rho +\int_{\rho_0}^{\rho_\text{max}}A\sqrt{\frac{\rho_0}{\rho}} \sqrt{\frac{1+\rho^2}{\rho^3}}\,d\rho\\ &= \frac{A}{\sqrt{\rho_0}} \int_{1/\rho_\text{max}}^{\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho +A\sqrt{\rho_0} \int_{1/\rho_\text{max}}^{1/\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho\\ \end{align*}

We derive with respect to $\rho_0$ \begin{align*} \frac{2s_\text{max}}{A\sqrt A}\frac\partial{\partial\rho_0} \mathbb E[\operatorname{overlap}] &=\frac{-1}{2\rho_0\sqrt{\rho_0}} \int_{1/\rho_\text{max}}^{\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho +\frac{1}{\sqrt{\rho_0}} \sqrt{\frac{1+\rho_0^2}{\rho_0^2}}\\ &\qquad +\frac 1{2\sqrt{\rho_0}} \int_{1/\rho_\text{max}}^{1/\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho +\sqrt{\rho_0} \times \frac{-1}{\rho_0^2} \times \sqrt{1+\rho_0^2} \\ \frac{4s_\text{max}\sqrt{\rho_0}}{A\sqrt A}\frac\partial{\partial\rho_0} \mathbb E[\operatorname{overlap}] &= \int_{1/\rho_\text{max}}^{1/\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho -\frac{1}{\rho_0} \int_{1/\rho_\text{max}}^{\rho_0} \sqrt{\frac{1+\rho^2}{\rho^2}}\,d\rho\\ &= \int_{\rho_0}^{\rho_\text{max}} \frac{\sqrt{1+\rho^2}}{\rho^2}\,d\rho -\frac 1{\rho_0} \int_{1/\rho_0}^{\rho_\text{max}} \frac{\sqrt{1+\rho^2}}{\rho^2}\,d\rho \\ &= \left[ -\frac{\sqrt{1+\rho^2}}{\rho} \right]_{\rho_0}^{\rho_\text{max}} +\int_{\rho_0}^{\rho_\text{max}} \frac 1{\sqrt{1+\rho^2}}\,d\rho\\ &\qquad +\frac 1{\rho_0} \left[\frac{\sqrt{1+\rho^2}}{\rho}\right]_{1/\rho_0}^{\rho_\text{max}} -\frac 1{\rho_0} \int_{1/\rho_0}^{\rho_\text{max}} \frac 1{\sqrt{1+\rho^2}}\,d\rho\\ &= \frac{\sqrt{1+\rho_0^2}}{\rho_0} -\frac{\sqrt{1+\rho_\text{max}^2}}{\rho_\text{max}} +\frac 1{\rho_0}\left( \frac{\sqrt{1+\rho_\text{max}^2}}{\rho_\text{max}} -\rho_0 \sqrt{\frac{1+\rho_0^2}{\rho_0^2}} \right)\\ &\qquad +\big[\text{arsinh}(\rho) \big]_{\rho_0}^{\rho_\text{max}} -\frac 1{\rho_0} \big[\text{arsinh}(\rho) \big]_{1/\rho_0}^{\rho_\text{max}}\\ &=\left( \frac 1{\rho_0} -1\right) \left( \frac{\sqrt{1+\rho_\text{max}^2}}{\rho_\text{max}} -\text{arsinh}(\rho_\text{max}) \right) +\text{arsinh}(\rho_0) -\frac{\text{arsinh}(1/\rho_0)}{\rho_0}\\ &=\frac{-1}{\rho_0}\left( \text{arsinh}(1/\rho_0) -C \right) +\left( \text{arsinh}(\rho_0) -C\right) \end{align*}

Where $C=\frac{\sqrt{1+\rho_\text{max}^2}}{\rho_\text{max}} -\text{arsinh}(\rho_\text{max})$. Let the function $g$ be defined by $g(t)=\text{arsinh}(t)-C$, it is strictly increasing. The sign of the derivative is given by the sign of $g(\rho_0) -\frac 1{\rho_0} g(1/\rho_0)$.

When $\rho_0<1$, we have $\rho_0<1<\frac 1{\rho_0}$ and $g(\rho_0)< g(1/\rho_0)< \frac 1{\rho_0}g(1/\rho_0)$. Hence the derivative is positive. When $\rho_0>1$, we have $g(\rho_0)> g(1/\rho_0) > \frac 1{\rho_0}g(1/\rho_0)$ and the derivative is negative. Within the range $1/\rho_\text{max}$ to $\rho_\text{max}$, $\rho_0=1$ is thus a local maxima. We should also check outside the range, but the computation is simpler in those cases. Anyway, the square yields the global maxima.

Computation - counter-exemple (general case)

Edit: changed to something else completely because the previous was false.

Assume you take some pdf function that is null around values of 1. Let's say there exists some $X>1$ such that for all $\frac 1X\le \rho\le X$, $\operatorname{pdf}(\rho) = 0$. In words, rectangles that look like a square have little probability of occuring, whereas skewed rectangles occur frequently. Now say you pick a rectangle whose ratio is close to a square, specifically its ratio $\rho_0$ is between $1/X$ and $X$.

\begin{align*} \mathbb E[\operatorname{overlap}] &=\int_0^{+\infty}f(\rho,\rho_0)\operatorname{pdf}(\rho)\,d\rho\\ &=\int_0^{1/X}f(\rho\le\rho_0)\operatorname{pdf}(\rho)\,d\rho +\int_{1/X}^{X}f(\rho,\rho_0)\operatorname{pdf}(\rho)\,d\rho +\int_{X}^{+\infty}f(\rho\ge\rho_0)\operatorname{pdf}(\rho)\,d\rho\\ &=\int_0^{1/X}A\sqrt{\frac\rho{\rho_0}}\operatorname{pdf}(\rho)\,d\rho +0 +\int_{X}^{+\infty}A\sqrt{\frac{\rho_0}\rho}\operatorname{pdf}(\rho)\,d\rho\\ &=\int_0^{1/X}A\sqrt{\frac\rho{\rho_0}}\operatorname{pdf}(\rho)\,d\rho +\int_{0}^{1/X}A\sqrt{\rho_0\rho}\operatorname{pdf}(\rho)\,d\rho\\ &=\left(\frac 1{\sqrt{\rho_0}}+\sqrt{\rho_0}\right) \times\int_0^{1/X}A\sqrt{\rho}\operatorname{pdf}(\rho)\,d\rho \\ &=\left(\frac 1{\sqrt{\rho_0}}+\sqrt{\rho_0}\right)\times C \end{align*}

Where $C$ is a constant independent from $\rho_0$. We then just have to study the variations of $\rho_0 \mapsto \sqrt{\rho_0}+1/\sqrt{\rho_0}$ which clearly isn't maximum for $\rho_0=1$ (the square case). The above may suggest that the maximum is reached for $\rho_0=0$ or $+\infty$, but that's not the case. The formula is only valid for $\frac 1X\le\rho_0\le X$ so we need to recompute it when we get out of these bounds.

Discussion

To put some sense into the result, just imagine every rectangles in the family $R$ is very skewed. If you pick a square it will overlap very little of every rectangles. On the other hand if you pick a rectangle whose skew agrees with (half of) the family, you will cover a lot of area (and compensate for the fact you ignore half of the family).

$\endgroup$
  • $\begingroup$ Thanks N. Bach. In the last part of the proof where you took, g be the increasing function and showed that differentiation of expectation with ρ0 is >= 0, is bit unclear to me. To be more specific, g(ρ0)≤ρ0g(1/ρ0) of given inequality, I am unable to understand why it will be that. If you can explain little more of this part, it will be great. Also, if you can given idea on how to show differentiation of expectation <= 0 for ρ≥1 .. Thanks again! $\endgroup$ – sanket Jun 3 '17 at 18:48
  • $\begingroup$ @sanket Re-reading it, looks like a mistake on my part, so my proof is wrong. Gonna check if I have some way out of this. $\endgroup$ – N.Bach Jun 3 '17 at 18:58
  • $\begingroup$ @sanket I've updated my answer... trying to prove something false has always been a good exercise in futility! $\endgroup$ – N.Bach Jun 3 '17 at 21:02
  • $\begingroup$ The counter example is based on the case that probability of skewed rectangles is more than one whose shapes are close to square . But in the question, it is said that all rectangles are equally likely. So all rectangles are possible along with their flip versions $\endgroup$ – sanket Jun 5 '17 at 22:52
  • $\begingroup$ @sanket "All rectangles being equally likely" usually means uniform distribution, but that's impossible because the range of parameter in the family is always unbounded. The only ways to paremeterize it that come to mind are using the ratio (like I did), the height, width or even perimeter, but all of those range to $+\infty$, so there are no uniform distribution. If you didn't mean uniform distribution, you'll have to be more specific. $\endgroup$ – N.Bach Jun 6 '17 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.