Regarding the case with 4 points on a plane, lets say (0,0), (0,10), (10,0), and (10,10), that are to be connected with a curve (or in graph theory terms it'd look like a spanning tree), provided I interpreted this properly, I first tried out a few options just to see what I get with them. I started with an X shape connecting the 4 corners, which ended up at around 28.284... miles, and connecting them with 2 vertical lines/streets (0,0) with (0,10) and (10,0) with (10,10), together with 1 horizontal line/street e.g. like (0,0) to (10,0) which simply gives 30 miles (and is aswell too much). As next step I thought about a free variable that I had at hand with my latter approach, namely the height or the horizontal connection which I could take more centered so it connects the other street segments from (0,5) to (10,5). And from there, one could take the existing street segment structure (consisting of 5 segments) and take the 2 points at which 3 segments each connect, namely these points (0,5) and (10,5) and then pull them horizontally inwards closer to the center (5,5), and let the street segment angles adapt accordingly. And then I remembered the theorem about the optimal parquetting of the flat 2D plane the way the bees do it using hexagonal structures as shortest paths to decompose the entire 2D plane into disjoint subsets with maximized volume while their boundary is minimized (iirc). And from there on, I thought it'd probably be a good idea to embed the 4 given points with their relative positions into such a hexagonal structure. I took an angle of 60°, or analogously 2*pi/6 = pi/3 between the x-axis (in reference to the coordinates that I gave the points/cities) and the straight line that would be defined as the street connection from the origin (0,0) to the horizontally rightwards pulled street segment connection point (0,5) which would then have some position (p,5) where it turns out that p = (5*sqrt(3))/3 = 2.886751346... (''p'' for the via horizontal ''pull'' gained new x-coordinate of the previous point (0,5)). Then with some trigonometry, one can calculate the length of the 4 outer street segments which is 4 times the same, together with the inner horizontal street segment which for general angle alpha gives as total street length the formula L = 10*(1+(2-cos(alpha))/sin(alpha))). (In here, L means the total length of the street, in miles.) And for the special case that I chose, alpha=pi/3 (which was good enough, but yeah with some analysis and derivatives and zeroes to find minima, one could check this part out in more detail), I get 10*(1+sqrt(3)) = 27.32050808... < 28 (miles).
For the generalized case I'd try to take the hexagonal grid structure and attempt to match it as closely as possible to the given set of points/cities that are provided.
Edit: Looks like we, me and BrunoVisnadi, got to the same solution :)
Many more edits: Regarding BrunoVisnadi's math problem, the thing that comes to mind first for me would be a the boundary of a perfect circle centered around the origin that exactly uses up the maximum street length, but some star shapes emerging from the origin might aswell be a good candidate (provided the streets all need to be connected). Thinking about it, the solution might be consisting of 3 street lines emerging outwards from the origin at angle 0°, 120° and 240° (like the situation at a corner of the hexagonal grid that covers a flat 2D plane). Maybe one could improve it further by bending the ends of such 3 line segments (emerging from the origin) let's say clockwise by 60° to help decreasing the distance to the corresponding 3 furthest away (from the street system) points of the 2D ball (or city) at the angles (0+60)°, (120+60)° and (240+60)° though (and one might only need to bend those three each in 1 direction instead of splitting up the ends of the 3 line segments at 60° in both ways, clockwise and counterclockwise, possibly because the increasing distance to another new set of 3 points by only bending the 3 line segments all in (the same) clockwise manner probably can be made up for a bit due to the circular repetition so that the line segment that is 120° counterclockwise to a given line segment also bends in that direction), but I'd not be sure at what point it'd make the most sense to do so, and it makes me think of 3 spirals that move outwards from the origin with some maybe constant curvature (adapted to the circumference of the city, but I kind of doubt a constant curvature, which would make each of the 3 spirals end up as circles if one would continue them, fits for this optimization), or maybe rather to 0 decreasing curvature the further one moves outwards (for larger and larger choices of city circumferences), such that the 3 spirals are offset by 120° (respectively 240°), but I'm a bit sceptical about the use of a structure that is curved instead of consisting just of straight line segments. And I'm also not sure at which part one should be cutting off such spirals then (if one would use them).
When I think of this math problem in a dynamical way, then as soon as 3 straight lines grow outwards from the origin like above, immediately 3 corresponding points can be determined that maximize the distance to the streets structure, so one could ''assign tasks'' to each of the 3 outwards growing curves, such that they each "hunt down" or bend towards 1 of the 2 distanct-maximizing closest outer points (let's say the clockwise one among the nearest, each) which will in turn cause 3 new distance-maximizers as points at the circumference of the city to be points that emerge from the initial ones by clockwise movement along the circumference (i.e. the "worst points" should be travelling around the circumference, and be updated every time one adapts to the previous ones by bending towards them).
A reason for why bending might be helpful could be the following: If one takes 3 line segments emerging from the origin at angles 0°, 120° and 240°, and e.g. takes the outer most point at angle 60°, then it will have the same distance to 2 end points of the street system, which means for this 1 point its distance to the street system will not get worse if one only bends 1 of the 2 nearest line segments towards or away from it, and then one can try to continue in this manner (update: but unfortunately the distance to points on the other side that one is bending away from becomes larger accordingly).
So since (in my currently chosen setting) the total length is what one can "spend" for either stronger curvature of 3 spirals that then don't reach as far outwards but bend heavily/quickly towards new updated "worst points", or weaker curvature for spirals that can reach further outwards but don't bend as much towards "new updated worst points that constitute distance-maximizers to the street system", the solution might be about finding the proper balance between these 2 cases.
(Also, one could apply or do this with 2 line segments/spirals with 180° degree offset too, or 4 or more of them, but 3 intuitively seemed like the best choice to me.)
Maybe the best "balance" of these 2 principles (growing outwards, to maximize the distance of the end points of the spirals to the origin; and the other would be to increase the curvature) would be reached when the speed with which the 3 worst points travel along the circumference is the same as the speed with which the end points of the curves grow their distance to the origin?
Okay an update: My brother (using some calculations) think's 4 spirals (with the same approach otherwise) would be better than 3. He also is more inclined to continue the approach using a ring around the origin, but cutting a segment of its circumference off (not quite a half-ring but an almost fully closed ring).
My brother also observed that for the process in which the city's radius diverges towards +infinity, that one is basically dealing with the distance between the all points within the city and the convex hull of the points part of the street system, since if one takes the pythagorean distance and corresponding circles, then the radius of these circles will grow larger and larger which makes the curvature become smaller and smaller and effectively end up being equivalent to straight lines that make up the boundary of the convex hull of the points that make up the street system. And because of this, taking the convex hull (so adding some more points) instead of just the street system doesn't gain one much (i.e. is a negligible difference) in the process of a growing city radius.
Actually, if one takes 4 straight lines outwards from the origin (all 4 of same length, along the 2 axes) and takes the 4 end points, then the connecting of the street system such that one can keep these 4 end points is improvable exactly the way as in the previous math problem stated by FractalFusion. (Which means one then can use remaining street length to expand the end points further outwards.) So maybe the same structure is the solution here, if one sets the origin into the center of BrunoVisnadi's graph's street structure.
collect, analyse, categorise.
"Mathematics - When tool-assisted skills are just not enough" ;)
Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on.
1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans.
2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai.
(last updated: 18.03.2018)
When the segment in the middle is (5/3)sqrt(3) miles long, the road's length is 10 + 10sqrt(3), so it costs you about $27.32 million.
This reminded me of an problem (for which I don't have an answer) I thought a few months ago that's also about optimizing a road:
Consider a circular town of radius 1 mile. You want to build a 1 mile length road inside this town. What is the smallest d for which you can build a road so that every point inside the town is at most d miles away from the street?
And perhaps an easier question: as the radius of the town goes to infinity, what will be the shape of the road that minimizes d?
The pentagon case (n=5) is discussed on this site. The solution for n=5 is shown below:
However, it turns out that for n≥6, the minimal Steiner tree is just the polygon on the points minus an edge. (Just because a Steiner tree satisfies all the properties above doesn't mean that it has minimum length!) More information is in this paper. The case n=6 has some local minima, but hexagon minus an edge is the minimum:
As for BrunoVisnadi's problem, assuming the road must be connected, I have so far a value of d≈0.812, where d=1-cos(x) and x is the root of cos(x)(pi-x+1)+sin(x)-1.5 in [0,pi/2]. The road I have is a "broken circle", having the shape of a hairband (I don't know how to describe it better). I'll explain how I got this later.
All of them asymptotically approximate the identity function for x to +infinity. For negative c they start below and for positive c above it. Notice that if the curve lies above the graph of the identity function, it is closer to the upper left part of the graph of the hyperbola, and to make up for this, the slope (or derivative) at every point on the graph is smaller than 1 but converges to 1 as the curve proceeds to the far right.
Here, d is the distance we want every point in the town to be within the road, r=1-d is the radius of the inner circle, P is a point on the edge of the town (here oriented at the top of the circle), and PA and PB are tangent lines to the inner circle. Then the road is formed by the arc AB (away from P) joined to the line segments from A and B toward P up to a distance of d away from P. The length of PA and PB are each sqrt(1-r2), and so the length of the road is:
r(2π-2θ) + 2(sqrt(1-r2)-(1-r)) = 2r(π-θ+1) + 2sqrt(1-r2) - 2.
Since cos(θ)=r and r=1-d, this becomes:
2(1-d)(π-cos-1(1-d)) + 2sqrt(2d-d2) - 2d.
Using WolframAlpha, when the above is set to 1, you get d≈0.812.
I checked some of the star-like configurations that Aran Jaeger suggested, but I couldn't do any better than this road with them, even with other values for d or length of road.
Now if you use d=0.5, you get 2π/3 - 1 + sqrt(3) ≈ 2.826. So in the case of general d, this method works for any length up to about 45% of the town's outer boundary. Beyond that, the question becomes complicated since now you need the road to cover the center of the town. All I know that, in the limiting case where d→0, parallel lines spaced 2d apart ensure that each point in the town is within d of some line. In this system, a road of length x is in proportion to an area of 2dx, the ratio of road to area being 1/(2d). So, given a circular town of radius 1, the length of the road required for some d close to 0 approaches 1/(2d) * 2π = π/d.
