7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ In $\mathbb{R}^3$, would you be seeking the maximum surface area of the hull, or the maximum volume? $\endgroup$
    – Joseph O'Rourke
    Commented Sep 19, 2014 at 18:12
  • $\begingroup$ I automatically thought of the volume. But definitely also a nice idea to wonder about maximizing the surface! $\endgroup$
    – Wolfgang
    Commented Sep 19, 2014 at 18:31
  • $\begingroup$ 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." $\endgroup$
    – Joseph O'Rourke
    Commented Sep 19, 2014 at 23:16
  • $\begingroup$ @JosephO'Rourke I cannot see how to introduce a lattice. In my setting, all segments composing the tree have the same length. $\endgroup$
    – Wolfgang
    Commented Sep 20, 2014 at 9:10

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Wolfgang
    Commented Sep 21, 2014 at 19:41
  • $\begingroup$ And even for $n=5$, taking 5 sides of an octagon yields an area $2\sqrt{3}(1+\sqrt{2})\approx8.36>8.$ $\endgroup$
    – Wolfgang
    Commented Sep 22, 2014 at 6:48
  • $\begingroup$ 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"! $\endgroup$
    – Wolfgang
    Commented Sep 22, 2014 at 7:06
1
$\begingroup$

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

  OrthoTrees

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 :) $\endgroup$
    – Wolfgang
    Commented Sep 20, 2014 at 19:28
  • $\begingroup$ @Wolfgang: Apologies for that misdirection. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 20, 2014 at 19:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wolfgang
    Commented Sep 20, 2014 at 19:36
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Wolfgang
    Commented Sep 22, 2014 at 6:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .