Joining the points of regular polygons

[david_uwi]

What is the minimum length of lines required to join the points of a regular polygon?
3 (triangle) is fairly easy, but what about a square (or a pentagon)?
As I was going through my old programs I found this (below) to do a triangle (iteratively).
The puzzle is normally phrased as a road building exercise - what is the minimum length of road needed to join four towns which happen to be at the vertices of a square.
So as a challenge can you do the same for 4 towns as I have done for 3. If that is too easy try 5.

Code: QB64: [Select]

1. SCREEN 12
2. nn = 3
3. rsummin = 10000: m = 1: n = 200
4. RANDOMIZE TIMER
5. WHILE m < 1000
6.     x1 = (RND * 360)
7.     y1 = (RND * 300)
8.     IF m > 2 THEN
9.         x1 = xa - n / m + RND * 2 * n / m
10.         y1 = ya - n / m + RND * 2 * n / m
11.     END IF
12.     m = m + .1
13.     x(1) = 60: y(1) = 300
14.     x(2) = 360: y(2) = 300
15.     x(3) = 210: y(3) = 40
16.     FOR i = 1 TO nn
17.         r(i) = SQR((x1 - x(i)) ^ 2 + (y1 - y(i)) ^ 2)
18.     NEXT i
19.     rsum = r(1) + r(2) + r(3)
20.     IF rsum < rsummin THEN
21.         rsummin = rsum
22.         xa = x1: xb = x2: ya = y1: yb = y2
23.         m = m + 1
24.         CLS
25.         FOR i = 1 TO nn
26.             CIRCLE (x(i), y(i)), 10
27.             LINE (x1, y1)-(x(i), y(i))
28.         NEXT i
29.         CIRCLE (x1, y1), 5
30.         LOCATE 1, 1
31.         q1 = SQR((x(1) - x(3)) ^ 2 + (y(1) - y(3)) ^ 2)
32.         q2 = SQR((x(2) - x(3)) ^ 2 + (y(2) - y(3)) ^ 2)
33.         PRINT rsummin * 20 / (q1 + q2)
34.         tt = TIMER
35.         WHILE TIMER - tt < .2: WEND
36.     END IF
37. WEND
38. LOCATE 3, 1
39. PRINT "Finished"
40. xx$ = INPUT$(1)
41.  

[STxAxTIC]

This sounds like calculating the centroid of a set of points, is that wrong?

[david_uwi]

No, you will find for a square that the shortest distance is not drawing two diagonals.
So if the sides of the square are 10. Around the perimeter is 30, drawing two diagonals is 28.28 (approx). Surprisingly there is an even shorter way.

[STxAxTIC]

Fascinating! I'm gonna play with this (on paper using calculus for N points). Maybe someone can demo up the N=4 case before I crack the general problem.

[STxAxTIC]

Hmmm, I kept on reproducing the centroid case for the answer to this on the back of some legal documents I ignore - but anyway - I'm still working on intuitively seeing it. Like if I start with a solved case and then introduce a new point very far away, how does the answer change? Mathematical intuition aside, I configured your code for N=4 points on a square, and sure enough, it gave me the centroid. What am I not getting? (See attached)

[SMcNeill]

What am I not getting? (See attached)

Warp drive?  ;D

(I couldn’t resist. :P)

Actually, I’d guess maybe a 3/4 circle with the polygon inside it.  Take the square and draw a “C” to connect the points....

Maybe..

[STxAxTIC]

Is there something about the phrasing of the question that might not have transcribed? If not the centroid, this only reminds me of the traveling salesman problem.

[bplus]

No, you will find for a square that the shortest distance is not drawing two diagonals.
So if the sides of the square are 10. Around the perimeter is 30, drawing two diagonals is 28.28 (approx). Surprisingly there is an even shorter way.

I get 28.28... also and it would be a surprise if it were less. Are you saying there is a point other than middle that connects to each of the other 4 points and the distance of all lines is less than 28.28...?

BTW perimeter is 40.

[bplus]

Oh wait I remember this, there are two points in the middle area and 120 degrees goes from two of corners to one middle point and line from that middle point to the other which connects the other 2 corners:


      \_/
      / \

But that makes more sense with rectangle.

update: I should say the lines from a middle point are all 120 degrees from each other = 360 total angle.

[STxAxTIC]

Translation of 28.28 = 4 * 10 * sqrt(2) / 2

[STxAxTIC]

Ah, that's a new angle. I bet that's what the problem is actually about. Even if not, that's interesting as hell.

EDIT: Oh boy, I see a dirty way to do this, and another way that's... crap there might go my week if I'm not careful.

If there's a pattern at all yet, we might have

Code: QB64: [Select]

1. 2 points                          - requires 0 nodes
2. 3 points in equilateral triangle  - requires 1 node
3. 4 points making a square          - requires 2 nodes
4. 5 points as a pentagon            - 3?
5.  

And then there's this technique - plot the given points as given, and then let there be a bunch, who cares - 1000 proposed nodes that connect to every single point and every other node, and these can move. This foregoes keeping track of vectors as a useful exercise, but what I *did* notice is that the correct solution minimizes ink on the page, supposing overlapping dots and lines are drawn once. I'm not sure if I can capture this in an equation without just using a program.

[bplus]

hyp * cos(30) = 5   then hyp = 5/cos(30) = 5.7736... x4 = 23.0946... for 4 corner lines

line in middle = 10 - 2 * (5.77 * sin(30) = 2.885) = 10 - 5.77 = 4.23

total of 5 lines = 23.0946 + 4.23... = 27. 32... < 28.28!

Using my numbers and scale 1 unit = 40 pixels our 10x10 gets mapped out like this:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(500, 500, 32)
2. LINE (50, 50)-(450, 450), , B '400 side  / 40 = 10
3.  
4. drawLine 50, 50, 60, 40 * 5.77
5. drawLine 450, 50, 120, 40 * 5.77
6. drawLine 450, 450, 240, 40 * 5.77
7. drawLine 50, 450, 300, 40 * 5.77
8. LINE (2.885 * 40 + 50, 5 * 40 + 50)-STEP(4.23 * 40, 0)
9.  
10. SUB drawLine (x, y, degreeAngle, dist)
11.     x1 = x + dist * COS(_D2R(degreeAngle))
12.     y1 = y + dist * SIN(_D2R(degreeAngle))
13.     LINE (x, y)-(x1, y1)
14. END SUB
15.  

[STxAxTIC]

Right, that's more like it.

I keep trying to approach this problem in a discrete math kind of way before turning to code. Here's something interesting - david asks about regular polygons, a handful of which can tile the 2D plane. If I cover an XY grid with squares, well, I can also cover it with the solution, making hexagons and diamonds if you draw it. So - is there anything about one tiling that leads to the other without knowing ahead of time that they are connected by the answer to this problem?

EDIT

Maybe minimizing the total length of road tends to maximize a particular area in a tiling scheme.

[bplus]

Here is my purposed road system for a Pentagon, can anyone find better = shorter?

Code: QB64: [Select]

1. _TITLE "Road to Pentagon" 'b+ 2020-02-05 in search of shortest road system to rech all points of Pentagon
2. SCREEN _NEWIMAGE(500, 500, 32)
3. TYPE xy
4.     x AS SINGLE
5.     y AS SINGLE
6. END TYPE
7. DIM p(4) AS xy
8.  
9. polygon 250, 250, 200, 5, _PI(-1 / 10), p(), side 'side = 235.1141
10. 'cos(30) = (235.1141/2) / h
11. hyp = (235.1141 / 2) / COS(_D2R(30))
12. drawLine p(1).x, p(1).y, 210, hyp, i1x, i1y
13. drawLine p(2).x, p(2).y, 330, hyp, i1x, i1y
14. LINE (p(3).x, p(3).y)-(p(0).x, p(0).y)
15. LINE (p(4).x, p(4).y)-(i1x, i1y)
16. D1 = SQR((p(0).x - p(3).x) ^ 2 + (p(0).y - p(3).y) ^ 2)
17. D2 = SQR((p(4).x - i1x) ^ 2 + (p(4).y - i1y) ^ 2)
18. LOCATE 29, 1: PRINT "Distance of 5 spokes or 5 * radius = 1000"
19. LOCATE 30, 1: PRINT "Sum of 4 inner lines here is"; D1 + D2 + 2 * hyp
20.  
21. SUB drawLine (x, y, degreeAngle, dist, x1, y1)
22.     x1 = x + dist * COS(_D2R(degreeAngle))
23.     y1 = y + dist * SIN(_D2R(degreeAngle))
24.     LINE (x, y)-(x1, y1)
25. END SUB
26.  
27. SUB polygon (xOrigin, yOrigin, radius, nVertex, RadianAngleOffset, p() AS xy, side)
28.     polyAngle = _PI(2) / nVertex
29.     p(0).x = xOrigin + radius * COS(RadianAngleOffset)
30.     p(0).y = yOrigin + radius * SIN(RadianAngleOffset)
31.     FOR i = 1 TO nVertex - 1
32.         p(i).x = xOrigin + radius * COS(i * polyAngle + RadianAngleOffset)
33.         p(i).y = yOrigin + radius * SIN(i * polyAngle + RadianAngleOffset)
34.         LINE (p(i - 1).x, p(i - 1).y)-(p(i).x, p(i).y)
35.     NEXT
36.     LINE (p(i - 1).x, p(i - 1).y)-(p(0).x, p(0).y)
37.     side = SQR((p(i - 1).x - p(0).x) ^ 2 + (p(i - 1).y - p(0).y) ^ 2)
38.     FOR i = 0 TO 4
39.         PRINT p(i).x, p(i).y
40.     NEXT
41.     PRINT " side:"; side
42. END SUB
43.  
44.  

[david_uwi]

Here's my solution...(it may find a false minimum occasionally so stick with it the length should be 38.91)
There is now a Wikipedia page on "Steiner trees" which rather gives it away.

https://en.wikipedia.org/wiki/Steiner_tree_problem
 

Code: QB64: [Select]

1. SCREEN 12
2. 'DEFDBL A-Z
3. nn = 5
4. rsummin = 10000: m = 1: n = 200
5. RANDOMIZE TIMER
6. WHILE m < 1000
7.     x1 = (RND * 300)
8.     y1 = (RND * 300)
9.     x2 = (RND * 300)
10.     y2 = (RND * 300)
11.     x3 = (RND * 300)
12.     y3 = (RND * 300)
13.     IF m > 2 THEN
14.         x1 = xa - n / m + RND * 2 * n / m
15.         x2 = xb - n / m + RND * 2 * n / m
16.         y1 = ya - n / m + RND * 2 * n / m
17.         y2 = yb - n / m + RND * 2 * n / m
18.         x3 = xc - n / m + RND * 2 * n / m
19.         y3 = yc - n / m + RND * 2 * n / m
20.     END IF
21.     m = m + .05
22.     RESTORE
23.     rsum = 0
24.     rmin1 = 10000: rmin2 = 10000: rmin3 = 10000: rmin4 = 10000: rmin5 = 10000
25.     pi = 3.141593
26.     nx = nn / 2
27.     FOR i = 1 TO nn
28.         ang = i * pi / nx + pi / nn
29.         x(i) = 150 - 150 * SIN(ang): y(i) = 150 - 150 * COS(ang)
30.         r(i) = SQR((x1 - x(i)) ^ 2 + (y1 - y(i)) ^ 2)
31.         IF r(i) < rmin1 THEN imin1 = i: rmin1 = r(i)
32.     NEXT i
33.     FOR i = 1 TO nn
34.         IF i = imin1 THEN 5
35.         IF r(i) < rmin2 THEN imin2 = i: rmin2 = r(i)
36.    5 NEXT i
37.  
38.     FOR i = 1 TO nn
39.         IF imin1 = i THEN 10
40.         IF imin2 = i THEN 10
41.         r(i) = SQR((x2 - x(i)) ^ 2 + (y2 - y(i)) ^ 2)
42.         IF r(i) < rmin3 THEN imin3 = i: rmin3 = r(i)
43.    10 NEXT i
44.     FOR i = 1 TO nn
45.         IF imin1 = i THEN 15
46.         IF imin2 = i THEN 15
47.         IF imin3 = i THEN 15
48.         IF r(i) < rmin4 THEN imin4 = i: rmin4 = r(i)
49.    15 NEXT i
50.     rsum = r(imin1) + r(imin2) + r(imin3) + r(imin4)
51.     FOR i = 1 TO nn
52.         IF imin1 = i THEN 20
53.         IF imin2 = i THEN 20
54.         IF imin3 = i THEN 20
55.         IF imin4 = i THEN 20
56.         r(i) = SQR((x3 - x(i)) ^ 2 + (y3 - y(i)) ^ 2)
57.         IF r(i) < rmin5 THEN imin5 = i: rmin5 = r(i)
58.    20 NEXT i
59.  
60.     rra = SQR((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
61.     rrb = SQR((x1 - x3) ^ 2 + (y1 - y3) ^ 2)
62.     rrc = SQR((x2 - x3) ^ 2 + (y2 - y3) ^ 2)
63.     a12 = 1: a13 = 2: a23 = 3
64.     IF rrb > rra THEN SWAP rra, rrb: SWAP a12, a13
65.     IF rrc > rra THEN SWAP rra, rrc: SWAP a12, a23
66.     IF rrc > rrb THEN SWAP rrc, rrb: SWAP a23, a13
67.     rsum = rsum + rrb + rrc + r(imin5)
68.     IF rsum < rsummin THEN
69.         rsummin = rsum
70.         xa = x1: xb = x2: ya = y1: yb = y2: xc = x3: yc = y3
71.         m = m + .5
72.         CLS
73.         FOR i = 1 TO nn
74.             CIRCLE (x(i) + 100, y(i) + 100), 10
75.         NEXT i
76.         CIRCLE (x1 + 100, y1 + 100), 5
77.         CIRCLE (x2 + 100, y2 + 100), 5
78.         CIRCLE (x3 + 100, y3 + 100), 5
79.         IF a12 <> 1 THEN LINE (x1 + 100, y1 + 100)-(x2 + 100, y2 + 100)
80.         IF a13 <> 1 THEN LINE (x1 + 100, y1 + 100)-(x3 + 100, y3 + 100)
81.         IF a23 <> 1 THEN LINE (x2 + 100, y2 + 100)-(x3 + 100, y3 + 100)
82.         LINE (x1 + 100, y1 + 100)-(x(imin1) + 100, y(imin1) + 100)
83.         LINE (x1 + 100, y1 + 100)-(x(imin2) + 100, y(imin2) + 100)
84.         LINE (x2 + 100, y2 + 100)-(x(imin3) + 100, y(imin3) + 100)
85.         LINE (x2 + 100, y2 + 100)-(x(imin4) + 100, y(imin4) + 100)
86.         LINE (x3 + 100, y3 + 100)-(x(imin5) + 100, y(imin5) + 100)
87.         LOCATE 1, 1
88.         rrr = SQR((x(1) - x(2)) ^ 2 + (y(1) - y(2)) ^ 2)
89.         PRINT rsummin * 10 / rrr
90.         tt = TIMER
91.         WHILE TIMER - tt < .13: WEND
92.     END IF
93. WEND
94. LOCATE 3, 1
95. PRINT "Finished"
96. xx$ = INPUT$(1)
97.