Timeline for Trees with a maximal convex hull: are the only optimal solutions Steiner trees?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 22, 2014 at 6:59 | comment | added | Wolfgang | 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$. | |
| Sep 20, 2014 at 19:36 | comment | added | Wolfgang | 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. | |
| Sep 20, 2014 at 19:33 | comment | added | Joseph O'Rourke | @Wolfgang: Apologies for that misdirection. | |
| Sep 20, 2014 at 19:28 | comment | added | Wolfgang | 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 :) | |
| Sep 20, 2014 at 19:20 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |