The following link claims the following
Show that you can place at most 16 points in a rectangle of size $\frac{D}{2} \times D$ such that no triangle formed from these points has a perimeter smaller than $D$.
How does one proceed to prove such a statement? I know that for the closest pair of points algorithm one can prove that a similar rectangle cannot contain more than 6 points and the proof for this can be arrived at using the intuition of placing circles as shown here. But what sort of argument can we make for triangles?
Can someone point me to the proof?
So I figured out a solution with some digging. Please correct me if I am wrong!
Theorem 1 Consider a square of dimensions $\frac{D}{4} \times \frac{D}{4}$. Any 3 points in this square form a triangle of perimeter less than $D$
Lemma 1 The triangle with maximum perimeter inscribed in a square is the one whose vertices are the square's vertices.
Proof : Consider any triangle $\Delta ABC$ inside the square $PQRS$. If we fix two vertices, say $A$ and $B$, and plot the locus of all points which will form a triangle with same perimeter as $\Delta ABC$, we will get an ellipse (sum of distance from foci is a constant). The larger the semi major axis of this ellipse, the larger the perimeter. The largest such ellipse that passes through some vertex of the square $PQRS$.
Now we can fix two other points of the new triangle and repeat the process till all three points lie on vertices of the square.
By Lemma 1, the largest perimeter of a triangle in a square with side $\frac{D}{4}$ is $\frac{D}{2} + \frac{\sqrt{2}D}{4} < D$
This proves Theorem 1.
We can divide a rectangle of dimensions of side $\frac{D}{2} \times D$ into 8 squares of side $\frac{D}{4}$ and each such square can contain at most 2 points. Thus such a rectangle can contain at most 16 points.
Q.E.D.