Line segments inside a squareFind a straight tunnelFind a straight tunnel 2Find shortest network connecting four pointsConnect four towers by roadsClash of arrowsQuadrilateral inside a squareInside or outside the square?IcosikaitrigonsA construction on an infinite 2d grid, part 1$verb|Eight Circles|$Form Common Geometric ShapesPentomino solution maximizing straight lines length in rectangle - wood cutter problem
Is the Wilcoxon rank-sum test a nonparametric alternative to the two sample t-test? Null hypotheses are different
How strong is XOR encryption of 256 bit plain text with 256 bit key?
How do you say "to play Devil's advocate" in German?
What is a short code for generating this matrix in R?
What is the purpose of the Dash 8’s “TOUCHED RUNWAY” warning light?
Decode the Dreaded Alphabet Cypher™️
Sold item on eBay, buyer wants it to be delivered to another country, and pay by bank transfer
Why does General Grievous say “Ah yes, the negotiator?”
Override iPhone's automatic brightness adjust?
What did the Oracle take from the Merovingian?
What are pros and cons around banning castling?
Can you control material visibility using another object?
Please help me spot the error in my "proof" that the sum of two irrational numbers must be irrational
How did the Corona (Key Hole) satellites film canisters deorbit?
How does a Mandalorian eat food if he never takes his helmet off?
Will transcribing music improve my ability to play a song by ear?
Estimating nest egg and inflation
My code seems to be a train wreck
How to compare the signature of two functions?
How to edit the website URL in Google Search Console
Altering an employment contract prior to signing
If thermodynamics says entropy always increases, how can the universe end in heat death?
Can I say "guess what" to acknowledge new information?
Should I perform my first oil before the manual says?
Line segments inside a square
Find a straight tunnelFind a straight tunnel 2Find shortest network connecting four pointsConnect four towers by roadsClash of arrowsQuadrilateral inside a squareInside or outside the square?IcosikaitrigonsA construction on an infinite 2d grid, part 1$verb|Eight Circles|$Form Common Geometric ShapesPentomino solution maximizing straight lines length in rectangle - wood cutter problem
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;
.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;
$begingroup$
A set of line segments inside or at the edge of a square with side length 1 should be positioned in such a way,
that any straight line going through the square must touch or intersect at least one of the line segment.
Find such a configuration where the total length of all such line segments is minimal?
Example: choose the 4 sides of the square as line segments. The length of those line segments is 4.
A better choice are the two diagonals of the square with a total length of $2timessqrt2$ ~ 2,828. Can you improve further?
geometry strategy
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
$endgroup$
add a comment
|
$begingroup$
A set of line segments inside or at the edge of a square with side length 1 should be positioned in such a way,
that any straight line going through the square must touch or intersect at least one of the line segment.
Find such a configuration where the total length of all such line segments is minimal?
Example: choose the 4 sides of the square as line segments. The length of those line segments is 4.
A better choice are the two diagonals of the square with a total length of $2timessqrt2$ ~ 2,828. Can you improve further?
geometry strategy
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
$endgroup$
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41
add a comment
|
$begingroup$
A set of line segments inside or at the edge of a square with side length 1 should be positioned in such a way,
that any straight line going through the square must touch or intersect at least one of the line segment.
Find such a configuration where the total length of all such line segments is minimal?
Example: choose the 4 sides of the square as line segments. The length of those line segments is 4.
A better choice are the two diagonals of the square with a total length of $2timessqrt2$ ~ 2,828. Can you improve further?
geometry strategy
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
$endgroup$
A set of line segments inside or at the edge of a square with side length 1 should be positioned in such a way,
that any straight line going through the square must touch or intersect at least one of the line segment.
Find such a configuration where the total length of all such line segments is minimal?
Example: choose the 4 sides of the square as line segments. The length of those line segments is 4.
A better choice are the two diagonals of the square with a total length of $2timessqrt2$ ~ 2,828. Can you improve further?
geometry strategy
geometry strategy
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
asked Sep 20 at 17:47
ThomasLThomasL
1,4962 silver badges21 bronze badges
1,4962 silver badges21 bronze badges
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41
add a comment
|
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41
add a comment
|
3 Answers
3
active
oldest
votes
$begingroup$
Building on LOTGP's answer, you could do this:
Assuming a unit square, the total length is:
The top left segment is $sqrt2/2$.
The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$sin45/sin120 approx 0.8164$ for the long sides
$sin15/sin120 approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+sqrt2/2 approx 2.707107$.
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
$endgroup$
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
add a comment
|
$begingroup$
Seems a slightly better solution would be to:
cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.
Something like this:
The total length is then:
1 + 1 + sqrt(2)/2 = 2.707
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
$endgroup$
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
add a comment
|
$begingroup$
Observation 1 (trivial):
There must be a segment touching each corner of the square
Observation 2 (non-rigorous):
Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).
Working assumption:
The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.
There is a structure that precisely realizes these needs:
A Steiner tree, which can be seen here:
The total length of segments is approx. 2.732
What is missing for optimality ( or: the dangers of intuition) ?
The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.
Update
After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f89359%2fline-segments-inside-a-square%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Building on LOTGP's answer, you could do this:
Assuming a unit square, the total length is:
The top left segment is $sqrt2/2$.
The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$sin45/sin120 approx 0.8164$ for the long sides
$sin15/sin120 approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+sqrt2/2 approx 2.707107$.
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
$endgroup$
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
add a comment
|
$begingroup$
Building on LOTGP's answer, you could do this:
Assuming a unit square, the total length is:
The top left segment is $sqrt2/2$.
The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$sin45/sin120 approx 0.8164$ for the long sides
$sin15/sin120 approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+sqrt2/2 approx 2.707107$.
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
$endgroup$
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
add a comment
|
$begingroup$
Building on LOTGP's answer, you could do this:
Assuming a unit square, the total length is:
The top left segment is $sqrt2/2$.
The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$sin45/sin120 approx 0.8164$ for the long sides
$sin15/sin120 approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+sqrt2/2 approx 2.707107$.
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
$endgroup$
Building on LOTGP's answer, you could do this:
Assuming a unit square, the total length is:
The top left segment is $sqrt2/2$.
The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$sin45/sin120 approx 0.8164$ for the long sides
$sin15/sin120 approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+sqrt2/2 approx 2.707107$.
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
edited Sep 20 at 21:32
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
answered Sep 20 at 21:17
Jaap ScherphuisJaap Scherphuis
22.7k1 gold badge40 silver badges94 bronze badges
22.7k1 gold badge40 silver badges94 bronze badges
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
add a comment
|
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
2
2
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.)
$endgroup$
– Bass
Sep 21 at 8:16
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
$begingroup$
Well done! If you use roots for the trigonometic values, you can write it as $$sqrt2+sqrt1.5$$
$endgroup$
– ThomasL
Sep 21 at 14:02
add a comment
|
$begingroup$
Seems a slightly better solution would be to:
cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.
Something like this:
The total length is then:
1 + 1 + sqrt(2)/2 = 2.707
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
$endgroup$
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
add a comment
|
$begingroup$
Seems a slightly better solution would be to:
cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.
Something like this:
The total length is then:
1 + 1 + sqrt(2)/2 = 2.707
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
$endgroup$
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
add a comment
|
$begingroup$
Seems a slightly better solution would be to:
cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.
Something like this:
The total length is then:
1 + 1 + sqrt(2)/2 = 2.707
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
$endgroup$
Seems a slightly better solution would be to:
cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.
Something like this:
The total length is then:
1 + 1 + sqrt(2)/2 = 2.707
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
answered Sep 20 at 18:01
LOTGPLOTGP
3561 silver badge7 bronze badges
3561 silver badge7 bronze badges
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
add a comment
|
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
$begingroup$
good finding! But I know that there is at least one more improvement...
$endgroup$
– ThomasL
Sep 20 at 20:20
add a comment
|
$begingroup$
Observation 1 (trivial):
There must be a segment touching each corner of the square
Observation 2 (non-rigorous):
Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).
Working assumption:
The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.
There is a structure that precisely realizes these needs:
A Steiner tree, which can be seen here:
The total length of segments is approx. 2.732
What is missing for optimality ( or: the dangers of intuition) ?
The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.
Update
After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
$endgroup$
add a comment
|
$begingroup$
Observation 1 (trivial):
There must be a segment touching each corner of the square
Observation 2 (non-rigorous):
Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).
Working assumption:
The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.
There is a structure that precisely realizes these needs:
A Steiner tree, which can be seen here:
The total length of segments is approx. 2.732
What is missing for optimality ( or: the dangers of intuition) ?
The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.
Update
After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
$endgroup$
add a comment
|
$begingroup$
Observation 1 (trivial):
There must be a segment touching each corner of the square
Observation 2 (non-rigorous):
Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).
Working assumption:
The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.
There is a structure that precisely realizes these needs:
A Steiner tree, which can be seen here:
The total length of segments is approx. 2.732
What is missing for optimality ( or: the dangers of intuition) ?
The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.
Update
After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
$endgroup$
Observation 1 (trivial):
There must be a segment touching each corner of the square
Observation 2 (non-rigorous):
Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).
Working assumption:
The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.
There is a structure that precisely realizes these needs:
A Steiner tree, which can be seen here:
The total length of segments is approx. 2.732
What is missing for optimality ( or: the dangers of intuition) ?
The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.
Update
After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
answered Sep 21 at 13:30
collapsarcollapsar
5232 silver badges7 bronze badges
5232 silver badges7 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f89359%2fline-segments-inside-a-square%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Technically we can calculus the line segments into curves if we so please.
$endgroup$
– greenturtle3141
Sep 20 at 20:26
$begingroup$
well, the line segments should be straight lines, if you want to clarify that.
$endgroup$
– ThomasL
Sep 20 at 20:33
$begingroup$
@greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines.
$endgroup$
– LOTGP
Sep 20 at 20:39
$begingroup$
Two related puzzles: Find a straight tunnel and Find a straight tunnel 2
$endgroup$
– Jaap Scherphuis
Sep 20 at 20:51
$begingroup$
Very nice one! Deceptively appears to be rather easy to solve ...
$endgroup$
– collapsar
Sep 21 at 13:41