Maximum Number of Points That Can be Packed in a Rectangle?Show that you can place at most 16 points in a rectangle of size D 2 × 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?

Question

Maximum Number of Points That Can be Packed in a Rectangle?Show that you can place at most 16 points in a rectangle of size       D    2    ×  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?

kliersel12g · Accepted Answer

Step 1So I figured out a solution with some digging. Please correct me if I am wrong!Theorem 1 Consider a square of dimensions       D    4    ×      D    4  . Any 3 points in this square form a triangle of perimeter less than DLemma 1 The triangle with maximum perimeter inscribed in a square is the one whose vertices are the square&#039;s vertices.Step 2Proof : Consider any triangle   Δ  A  B  C 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   Δ  A  B  C, 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       D    4   is       D    2    +                    2            D        4    &amp;lt;  D.This proves Theorem 1.We can divide a rectangle of dimensions of side       D    2    ×  D into 8 squares of side       D    4   and each such square can contain at most 2 points. Thus such a rectangle can contain at most 16 points.

Show that you can place at most 16 points in a rectangle of size D/2 times D such that no triangle formed from these points has a perimeter smaller than D.

Answered question

Answer & Explanation

New Questions in High school geometry