# Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $$n\geqslant 3$$, I'm looking for a connected set composed of $$n$$ equal segments in the plane such that the convex hull of it has maximal area $$A(n)$$. To simplify notation, we'll take $$\dfrac{2}{\sqrt[4]{3}}$$ as the length of each segment, so the unit triangle has area $$1$$.

It turns out that for small $$n$$, all the optimal solutions are Steiner trees, in the sense that each point belonging to more than one segment is the common endpoint of either two segments forming a straight line, or of three segments forming angles of $$\dfrac{2\pi}{{3}}$$. We'll call points of the latter kind branching points.

Using Steiner trees with only one branching point and the three legs of almost same length, we get the trivial lower bounds
$$\ \ \,\quad A(3k)\geqslant 3k^2$$,
$$A(3k+1)\geqslant k(3k+2)$$,
$$A(3k+2)\geqslant (k+1)(3k+1)$$.

Equally, we can write $$A(n)\geqslant \left[\frac{n^2}3\right]=$$ A000212 $$(n)$$. The oeis entry contains several interesting comments but nothing which immediately applies here.

For a given $$n$$, there can be other Steiner trees of same length with more than one branching point which yield the same area. It might be an interesting question how many non-isomorphic ones exist, but before that, I want to ask the following:

• Is this bound sharp for all $$n$$?

• Are there optimal solutions which are not Steiner trees?

(EDIT: in fact, for $$n=2,3,4$$ taking $$n$$ consecutive edges of a regular hexagon yields also optimal solutions, which I would however consider marginal.)
This is somewhat converse to the problem of Steiner minimal trees for convex polygons but not exactly.

The problem, the above construction and both questions can be immediately generalized to trees spanning volumes in $$\mathbb R^d$$ instead of $$\mathbb R^2$$. Conjecturally the answers are the same as for the plane.

• In $\mathbb{R}^3$, would you be seeking the maximum surface area of the hull, or the maximum volume? – Joseph O'Rourke Sep 19 '14 at 18:12
• I automatically thought of the volume. But definitely also a nice idea to wonder about maximizing the surface! – Wolfgang Sep 19 '14 at 18:31
• This may be a distraction, but I wonder if your question could be more easily answered on a lattice? You probably know there is work on lattice Steiner trees, e.g., "Minimal Steiner Trees for Rectangular Arrays of Lattice Points." – Joseph O'Rourke Sep 19 '14 at 23:16
• @JosephO'Rourke I cannot see how to introduce a lattice. In my setting, all segments composing the tree have the same length. – Wolfgang Sep 20 '14 at 9:10

One may ask an analogous continuous problem:

Which connected set composed of simple arcs of total length $1$ has the largest convex hull?

If my computations are correct, the star formed by three segments of length $1/3$ and forming the angles $2\pi/3$ gives a triangle of area $\frac{1}{4\sqrt{3}} \sim \frac{1}{6.93}$, whereas a half-circle of length $1$ gives a half-disc of area $\frac{1}{2\pi} \sim \frac{1}{6.28}$, which is larger.

This implies that for large enough $n$, the Steiner tree with one branching point is not optimal.

Edit: I just found that this problem has been solved in the special case that the connected set is a curve; see the following question: Largest convex hull of a unit length path

The three-dimensional case is discussed here: Largest possible volume of the convex hull of a curve of unit length

• Great approach and big surprise! It looks like you are right. For $n$ as small as $n=6$, taking half of a 12-gon yields an area $6+4\sqrt{3}\approx 12.93>12$. – Wolfgang Sep 21 '14 at 19:41
• And even for $n=5$, taking 5 sides of an octagon yields an area $2\sqrt{3}(1+\sqrt{2})\approx8.36>8.$ – Wolfgang Sep 22 '14 at 6:48
• Thank you also for the two links. After seeing your answer, I realized that this is closely related to those questions about curves in $\mathbb R^2$ or $\mathbb R^3$. How misleading it can be to stick too much to the idea of "trees"! – Wolfgang Sep 22 '14 at 7:06

Apologies for posting this potentially distracting non-answer, but I wanted to illustrate a possibly simpler problem on a lattice ($n=8$):

• OK, I see. So in fact you want the whole tree on a lattice. Definitely simpler! But this has nothing to do with the paper linked in your comment above then. (I had desperately tried to make a connection :) – Wolfgang Sep 20 '14 at 19:28
• @Wolfgang: Apologies for that misdirection. – Joseph O'Rourke Sep 20 '14 at 19:33
• Definitely simpler. If you move horizontal and vertical lines around (I mean the 'whole' lines), as long as they have a common point, the area doesn't change. So the maximal area here should be $n^2/8$ for n even and $(n^2-1)/8$ for n odd. – Wolfgang Sep 20 '14 at 19:36
• Even though elementary, this is interesting in the light of @Jan Kyncl's answer: for your variant of the problem, the "continuisation" wouldn't give anything. Take a large $n=4r$ and approach a half-circle of radius r by a lattice path. Then we can "bend out" the zigzag parts, maintaining the total length, until arriving at the circumscribed rectangle as hull, again with area $n^2/8$. – Wolfgang Sep 22 '14 at 6:59