4
$\begingroup$

Given the figure below, find the shortest network of straight line segments (like a Steiner tree, or like parts of a Delaunay triangulation) that connects the four circled points while staying in the purple region. No line in the network can cross or enter an area that isn't purple, but point contact is allowed.

green pentagram on purple caltrop

Note, the coordinates of the outer points of the green pentagram are [(29, 7), (2, 29), (-27, 11), (-19, -22), (15, -25)] (CCW from right), and the coordinates of the vertices of the purple figure are [(0, 100), (30, 30), (100, 0), (30, -30), (0, -100), (-30, -30), (-100, 0), (-30, 30)] (CW from top). Each square in the background grid is 10 x 10 units. Solution attempts can be given as drawings, but node coordinates are needed for objective comparisons of path length.

As an example, the figure below shows (in blue) a valid network of length 405.4 that is not minimal.

with blue network added; half scale

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

I can get approximately 389.6 with the following arrangement:

584

The lines from the bottom and leftmost points of the 4-sided star follow a little inside the edges of the purple region, the section between P and Q kinks a little as it just touches the top and upper right points of the star. Angles of the 3-point intersections at P and Q are all 120 degrees. Distances and positions shown in the diagram are approximate only. P = (-8.62246,37.24663); Q = (39.67114,-7.24132)

Correction: With P=(-8.622454731281,37.246624550459); Q=(39.671139293683,-7.241324684499) I now get a total distance of 389.739586527472 which I believe is accurate to approximately 11 decimal places.

Improve this answer
$\endgroup$
4
  • $\begingroup$ A minor issue -- my calculation of length is about 389.7396 (ie not 389.584) as follows. (-100.0000, 0.0000) to ( -8.6225, 37.2466) is 98.6771 long. ( -8.6225, 37.2466) to ( 2.0000, 29.0000) is 13.4478 long. ( 2.0000, 29.0000) to ( 29.0000, 7.0000) is 34.8281 long. ( 29.0000, 7.0000) to ( 39.6711, -7.2413) is 17.7957 long. ( 39.6711, -7.2413) to (100.0000, 0.0000) is 60.7619 long. ( 0.0000,100.0000) to ( -8.6225, 37.2466) is 63.3430 long. ( 39.6711, -7.2413) to ( 0.0000,-100.0000) is 100.8859 long. $\endgroup$
    – James Waldby - jwpat7
    Aug 25, 2014 at 5:47
  • $\begingroup$ @jwpat7 - You are correct, I made a digital transposition error when adding the individual lengths. Now I believe I can confirm the minimum distance is 389.739586527472 (accurate to ~11 palaces after the decimal) $\endgroup$
    – Penguino
    Aug 25, 2014 at 22:00
  • $\begingroup$ That's a lot of palaces $\endgroup$
    – James Waldby - jwpat7
    Aug 25, 2014 at 23:11
  • $\begingroup$ @jwpat7 Yep - very regal $\endgroup$
    – Penguino
    Aug 26, 2014 at 0:34
0
$\begingroup$

My first attempt had some mistakes, so here's my second attempt:-

Firstly lets consider the simpler case when the green pentagram is absent.This then corresponds to the case of the four points at the corner of a square and the solution is well-known and looks like this. I show the dashed red line to indicate the constraint that we face in our case.

enter image description here

In this case the the total path length is $\lambda_{simple}=386.37$. So we can conclude that for the constrained case the total path length has a lower bound given by $\lambda_{constrained}>\lambda_{simple}$.

Now when the constraint(green pentagram) is included we simply need to move the red dotted line shown in the previous figure outside the constrained space and this could be done as follows:

enter image description here

For this network configuration we get $\lambda_{constrained}=394.66$

I hope this time i have not made any obvious mistakes. I think this should be the minimum path length unless someone can find any in-between values $386.37<\lambda_{constrained}<394.66$

Improve this answer
$\endgroup$
3
  • $\begingroup$ You can remove the two lines at the bottom left - they're not necessary. $\endgroup$
    – isaacg
    Aug 24, 2014 at 7:31
  • $\begingroup$ Hubble07, I calculate 394.1 for that path ... and below 392 for other paths! $\endgroup$
    – James Waldby - jwpat7
    Aug 24, 2014 at 15:42
  • $\begingroup$ I think this is closer, but remember that you don't actually have to touch the inside diagram; if you move the contact points back to the inside points of the purple star, that, I think, would be possibly optimal. $\endgroup$
    – user20
    Aug 24, 2014 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.