Triangle (constrained number, rather than shape) packing?

Question

Are there any interesting results on optimal packings in the plane using a fixed number of triangles (without a fixed size or shape constraint)?

For instance, what's the maximum area packing of the unit circle using at most $N$ non-intersecting (except possibly on the boundary) triangles inside the circle? This isn't very difficult with the additional assumption that the vertices of the triangle all lie on the circumference (we can smooth the triangles "together" to form a triangulation of a $(N+2)$-gon, and either use Jensen or compactness and further smoothing to show the regular $(N+2)$-gon is optimal). But in the general case, smoothing seems much more difficult---the triangles can "block" each other in much more complicated configurations, which seem hard to classify.

Edit (8/18/14). First, a potentially fruitful (and quite nice!) idea from fedja copied from AoPS, which works for the semicircle case (i.e. packing into a semicircle rather than a circle):

Then [in the semicircle case] all you would need to do (assuming that the diameter is $[-1,1]$) would be to consider the vertical cross-sections and notice that their length is a piecewise linear function with at most as many "down" corners as we have triangles, dominated by $\sqrt{1-x^2}$, so we would have to estimate the area between the axis and a piecewise convex curve with a fixed number of pieces under the circular arc, and everything would become pretty obvious. I guess the idea has a good chance to work in the current setting too, but the details will, most likely, be much less elegant :(.

I might as well mention the corresponding MSE thread.

Also, here's a potentially serious obstruction to most smoothing arguments, from an email of Tim Chu's:

Take a small $N$-gon and extend the exterior angles.

Place it in at the center of a very big circle. Then you get a shape that's almost the same as if you made a regular $N$-gon by having all the triangles share one vertex at the center of the circle, except instead these $N$ triangles trace out a small $N$-gon in the center instead of meeting at a single point.

The problem is that in this arrangement, you can't smooth any single triangle to have a greater area [which is what the easiest smoothing approaches try to do]. So in a sense, this arrangement is "locally optimal" but not "globally optimal". In this case, it's rather clear that the example presented isn't actually optimal (namely, its area is bounded above by that of the $N$-gon), but there are other examples in this vein ("locally optimal" but not "globally optimal") in which it's not clear why they don't beat the $(N+2)$-gon.

(This example also breaks any approach that attempts to directly find two triangles $ABC$ and $DEF$ such that no other triangles intersect the convex hull of $ABCDEF$.)

Answer 1

We will prove that the $(n+2)$-gon is always the solution for $n$-triangles, by method of elimination.

Definitions:

$A_n$ is a solution satisfying the given conditions for $n$ triangles. By nature $A_n$ is a polygon or a collection of disjoint polygons.

$h(A_n)$ will denote the hull of $A_n$, while $ch(A_n)$ will denote the convex hull.

Proof:

We will start with a trivial, but nonetheless useful observation - if moving a set of vertices can increase the total area, $A_n$ is not a solution.

Any simple polygon with $n$-vertices consists of exactly $n-2$ triangles. Thus any simple polygon can be deformed into another simple polygon with the same amount of vertices, without changing the amount of triangles needed.

In general, if for a certain set of probable solutions, there exists a method to increase the area, then said set can be dismissed. On that we will begin:

1. $A_n$ cannot be a disjoint collection of polygons;

   Proof: if we connect said polygons, we will increase the total area.

2. The hull vertices of $A_n$ are convex.

   Proof: if $h(A_N)$ contains more vertices than $ch(A_n)$, then its worthwhile to substitute, as we will have more triangles to fill up the space.

3. Any "hole" in $A_n$ must have all its vertices in the $h(A_n)$;

   Proof: If we move a vertex of a polygon $P$, such that it doesn't create an intersection, overlap with another vertex, or lie on a segment generated by two other vertices, then the overall amount of triangles required for a triangulization of $P$ does not change.

   If we have a vertex in $A_n$, which is not in $h(A_n)$, then it can be moved onto it, reducing the amount of vertices, getting a spare triangle to fill up the space and increasing the span of $A_n$ edges.

4. $A_n$ touches the unit circle atleast once.

   Proof: Let $m$ denote the maximum distance from the origin of all vertices in $A_n$. Since we are dealing with the unit circle, the following must hold $m^{-1}A_n = A_n$, which means that the maximum length will always be $1$ or that $A_n$ touches the unit circle at least once.

   !! On a side note, one convincing idea arises - if $A_n$ can be covered up with a convex polygon with $n+2$ or less vertices, which are all on the circle, then $A_n$ is not a solution. If one imagines an arbitrary messy polygon dangling from one point off the unit circle, overlapped by a convex polygon, one is quite convinced how convex the hull of $A_n$ must be.

   So, we are left with "incomplete" triangulizations of simple convex polygons.

5. In a convex incomplete simple, all "holes" can be patched up with an increase in area.

   Proof: If we remove three adjacent vertices in a convex polygon, the remaining vertices are still in convex arrangement.

   First, we start with a lemma - the smallest area triangle in a convex polygon is always composed of three adjacent vertices - proof.

   Any "hole" is a polygon in $A_n$. By the lemma, it follows that we can always swap out all the constituent triangles of said polygon for the triangles composed of three adjacent vertices, increasing the area for each swap. Which in the end results in a simple convex polygon, with total greater area.

6. The largest simple convex polygon with $n$ triangles in the unit circle, is the $(n+2)$-gon.

   Proof: Extending any vertex of a simple convex polygon to the perimeter of the unit circle, increases the area. Thus all the vertices are on the circle.

   If we move a point $B$, in between two adjacent points $A$ and $C$, the area of $\Delta ABC$ will be maximum, when the altitude to $B$ is in the middle of $AC$. Therefore, any vertex on the unit circle is equally distanced from its neighbours.

   Such a configuration can only be achieved by the $(n+2)$-gon with $n$-triangles.

   Therefore, the $(n+2)$-gon, with all of its vertices on the unit circle, is the largest polygon that can be assembled from $n$-triangles.

Edit

(I apologize for lack of proper definitions, I had no one to check the proof with, so they just grew on me.) What is a hole and a hull?

Lets consider any candidate solution, $A_n$ (for now we will think of it as a polygon, not a collection of triangles), as a closed set in $\Bbb R^2$. Lets consider the boundary of $A_n$:

1. if we are dealing with a simple polygon, then the boundary, ∂$A_n$, is equivalent to the hull, $h(A_n)$;
2. If not, then the hull is a connected subset of the boundary, which contains the most area. If we then take the compliment ∂$A_n \setminus h(A_n)$, we can interpret it as the union of boundaries of closed sets, which are disconnected with $R^2$. We will call said sets holes;

For an interpretation of (3) - this is mostly an elaboration on the first observation, that if moving a set of vertices can increase the total area, $A_n$ is not a solution. This observation dismisses all holes, which are not attached to the hull, as we can simply "shrink" them into nothingness. However in the case, where a hole has vertices in the hull, then moving a free vertex onto a shared vertex, will give us another triangle, which we can use to fill up said hole.

Upon reviewing the solution again, I think I can just remove (3), since all cases covered by it can also be dismissed by the first observation or (5).

If anything else is unclear, please tell me, I would appreciate it greatly.