Four Dragon Curves are Edge-covering/Plane-tiling












6












$begingroup$


Four Dragon curves generating outwards from the same vertex will traverse every edge of a grid exactly once (and as a consequence will be plane-tiling as well).



enter image description here I am captivated by this fact, and somewhat wishfully suspect that there is a simple and illuminating explanation for it. If this is not the case, however, can anybody direct me to a resource where this is discussed in detail?...I cannot find the original articles by Chandler and Donald J. Knuth. "Number representations and dragon curves", on jstor.org :(



Here are a few quick links for reference:



http://mathworld.wolfram.com/DragonCurve.html



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



Historically, Dragon Curves were discovered in 1969 by two NASA engineers who were interested in the pattern produced by folding a piece of paper repeatedly and then unfurling it such that all the folds were manifested as right angles, a fundamental construction which I believe to be part of the key to intuitively understanding all these properties...










share|cite|improve this question











$endgroup$












  • $begingroup$
    Very interesting! But could you include a link or a definition of "Dragon Curves"
    $endgroup$
    – Mike
    Jan 6 at 20:28










  • $begingroup$
    Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
    $endgroup$
    – Math Enthusiast
    Jan 6 at 20:35












  • $begingroup$
    A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
    $endgroup$
    – Mark McClure
    Jan 7 at 1:04
















6












$begingroup$


Four Dragon curves generating outwards from the same vertex will traverse every edge of a grid exactly once (and as a consequence will be plane-tiling as well).



enter image description here I am captivated by this fact, and somewhat wishfully suspect that there is a simple and illuminating explanation for it. If this is not the case, however, can anybody direct me to a resource where this is discussed in detail?...I cannot find the original articles by Chandler and Donald J. Knuth. "Number representations and dragon curves", on jstor.org :(



Here are a few quick links for reference:



http://mathworld.wolfram.com/DragonCurve.html



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



Historically, Dragon Curves were discovered in 1969 by two NASA engineers who were interested in the pattern produced by folding a piece of paper repeatedly and then unfurling it such that all the folds were manifested as right angles, a fundamental construction which I believe to be part of the key to intuitively understanding all these properties...










share|cite|improve this question











$endgroup$












  • $begingroup$
    Very interesting! But could you include a link or a definition of "Dragon Curves"
    $endgroup$
    – Mike
    Jan 6 at 20:28










  • $begingroup$
    Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
    $endgroup$
    – Math Enthusiast
    Jan 6 at 20:35












  • $begingroup$
    A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
    $endgroup$
    – Mark McClure
    Jan 7 at 1:04














6












6








6


1



$begingroup$


Four Dragon curves generating outwards from the same vertex will traverse every edge of a grid exactly once (and as a consequence will be plane-tiling as well).



enter image description here I am captivated by this fact, and somewhat wishfully suspect that there is a simple and illuminating explanation for it. If this is not the case, however, can anybody direct me to a resource where this is discussed in detail?...I cannot find the original articles by Chandler and Donald J. Knuth. "Number representations and dragon curves", on jstor.org :(



Here are a few quick links for reference:



http://mathworld.wolfram.com/DragonCurve.html



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



Historically, Dragon Curves were discovered in 1969 by two NASA engineers who were interested in the pattern produced by folding a piece of paper repeatedly and then unfurling it such that all the folds were manifested as right angles, a fundamental construction which I believe to be part of the key to intuitively understanding all these properties...










share|cite|improve this question











$endgroup$




Four Dragon curves generating outwards from the same vertex will traverse every edge of a grid exactly once (and as a consequence will be plane-tiling as well).



enter image description here I am captivated by this fact, and somewhat wishfully suspect that there is a simple and illuminating explanation for it. If this is not the case, however, can anybody direct me to a resource where this is discussed in detail?...I cannot find the original articles by Chandler and Donald J. Knuth. "Number representations and dragon curves", on jstor.org :(



Here are a few quick links for reference:



http://mathworld.wolfram.com/DragonCurve.html



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



Historically, Dragon Curves were discovered in 1969 by two NASA engineers who were interested in the pattern produced by folding a piece of paper repeatedly and then unfurling it such that all the folds were manifested as right angles, a fundamental construction which I believe to be part of the key to intuitively understanding all these properties...







fractals tiling






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 7 at 0:57









Mark McClure

23.8k34472




23.8k34472










asked Jan 6 at 20:18









Math EnthusiastMath Enthusiast

1168




1168












  • $begingroup$
    Very interesting! But could you include a link or a definition of "Dragon Curves"
    $endgroup$
    – Mike
    Jan 6 at 20:28










  • $begingroup$
    Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
    $endgroup$
    – Math Enthusiast
    Jan 6 at 20:35












  • $begingroup$
    A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
    $endgroup$
    – Mark McClure
    Jan 7 at 1:04


















  • $begingroup$
    Very interesting! But could you include a link or a definition of "Dragon Curves"
    $endgroup$
    – Mike
    Jan 6 at 20:28










  • $begingroup$
    Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
    $endgroup$
    – Math Enthusiast
    Jan 6 at 20:35












  • $begingroup$
    A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
    $endgroup$
    – Mark McClure
    Jan 7 at 1:04
















$begingroup$
Very interesting! But could you include a link or a definition of "Dragon Curves"
$endgroup$
– Mike
Jan 6 at 20:28




$begingroup$
Very interesting! But could you include a link or a definition of "Dragon Curves"
$endgroup$
– Mike
Jan 6 at 20:28












$begingroup$
Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
$endgroup$
– Math Enthusiast
Jan 6 at 20:35






$begingroup$
Certainly! I'll add it right now, my preferred definition is the one from Wolfram which describes concatenation of binary strings, but there are many equivalent definitions as well @Mike
$endgroup$
– Math Enthusiast
Jan 6 at 20:35














$begingroup$
A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
$endgroup$
– Mark McClure
Jan 7 at 1:04




$begingroup$
A paper by Christoph Bandt explains how these types of constructions arise from expanding integer matrices.
$endgroup$
– Mark McClure
Jan 7 at 1:04










1 Answer
1






active

oldest

votes


















8












$begingroup$

Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.



figure 1



If we apply the same substitution rule to this infinite grid of arrows, we happen to get a smaller rotated copy of the same grid. After seeing it happen once, it’s obvious that it will continue to happen infinitely many times.



figure 2



Now we can color four arrows of the initial grid and watch them grow into four dragons:



figure 3



We’ve generated exactly the figure that you posted. But this construction makes it clear why they have to fit together this way—each arrow in the grid must be used exactly once.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
    $endgroup$
    – Math Enthusiast
    Jan 8 at 0:32






  • 1




    $begingroup$
    You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
    $endgroup$
    – Anders Kaseorg
    Jan 8 at 1:51










  • $begingroup$
    The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
    $endgroup$
    – Math Enthusiast
    Jan 13 at 22:14






  • 1




    $begingroup$
    @MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
    $endgroup$
    – Anders Kaseorg
    Jan 13 at 22:42










  • $begingroup$
    Ok thanks :) I thought you didn't see it sorry
    $endgroup$
    – Math Enthusiast
    Jan 15 at 1:11











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064350%2ffour-dragon-curves-are-edge-covering-plane-tiling%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









8












$begingroup$

Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.



figure 1



If we apply the same substitution rule to this infinite grid of arrows, we happen to get a smaller rotated copy of the same grid. After seeing it happen once, it’s obvious that it will continue to happen infinitely many times.



figure 2



Now we can color four arrows of the initial grid and watch them grow into four dragons:



figure 3



We’ve generated exactly the figure that you posted. But this construction makes it clear why they have to fit together this way—each arrow in the grid must be used exactly once.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
    $endgroup$
    – Math Enthusiast
    Jan 8 at 0:32






  • 1




    $begingroup$
    You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
    $endgroup$
    – Anders Kaseorg
    Jan 8 at 1:51










  • $begingroup$
    The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
    $endgroup$
    – Math Enthusiast
    Jan 13 at 22:14






  • 1




    $begingroup$
    @MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
    $endgroup$
    – Anders Kaseorg
    Jan 13 at 22:42










  • $begingroup$
    Ok thanks :) I thought you didn't see it sorry
    $endgroup$
    – Math Enthusiast
    Jan 15 at 1:11
















8












$begingroup$

Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.



figure 1



If we apply the same substitution rule to this infinite grid of arrows, we happen to get a smaller rotated copy of the same grid. After seeing it happen once, it’s obvious that it will continue to happen infinitely many times.



figure 2



Now we can color four arrows of the initial grid and watch them grow into four dragons:



figure 3



We’ve generated exactly the figure that you posted. But this construction makes it clear why they have to fit together this way—each arrow in the grid must be used exactly once.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
    $endgroup$
    – Math Enthusiast
    Jan 8 at 0:32






  • 1




    $begingroup$
    You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
    $endgroup$
    – Anders Kaseorg
    Jan 8 at 1:51










  • $begingroup$
    The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
    $endgroup$
    – Math Enthusiast
    Jan 13 at 22:14






  • 1




    $begingroup$
    @MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
    $endgroup$
    – Anders Kaseorg
    Jan 13 at 22:42










  • $begingroup$
    Ok thanks :) I thought you didn't see it sorry
    $endgroup$
    – Math Enthusiast
    Jan 15 at 1:11














8












8








8





$begingroup$

Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.



figure 1



If we apply the same substitution rule to this infinite grid of arrows, we happen to get a smaller rotated copy of the same grid. After seeing it happen once, it’s obvious that it will continue to happen infinitely many times.



figure 2



Now we can color four arrows of the initial grid and watch them grow into four dragons:



figure 3



We’ve generated exactly the figure that you posted. But this construction makes it clear why they have to fit together this way—each arrow in the grid must be used exactly once.






share|cite|improve this answer









$endgroup$



Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.



figure 1



If we apply the same substitution rule to this infinite grid of arrows, we happen to get a smaller rotated copy of the same grid. After seeing it happen once, it’s obvious that it will continue to happen infinitely many times.



figure 2



Now we can color four arrows of the initial grid and watch them grow into four dragons:



figure 3



We’ve generated exactly the figure that you posted. But this construction makes it clear why they have to fit together this way—each arrow in the grid must be used exactly once.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 7 at 0:25









Anders KaseorgAnders Kaseorg

79349




79349












  • $begingroup$
    This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
    $endgroup$
    – Math Enthusiast
    Jan 8 at 0:32






  • 1




    $begingroup$
    You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
    $endgroup$
    – Anders Kaseorg
    Jan 8 at 1:51










  • $begingroup$
    The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
    $endgroup$
    – Math Enthusiast
    Jan 13 at 22:14






  • 1




    $begingroup$
    @MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
    $endgroup$
    – Anders Kaseorg
    Jan 13 at 22:42










  • $begingroup$
    Ok thanks :) I thought you didn't see it sorry
    $endgroup$
    – Math Enthusiast
    Jan 15 at 1:11


















  • $begingroup$
    This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
    $endgroup$
    – Math Enthusiast
    Jan 8 at 0:32






  • 1




    $begingroup$
    You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
    $endgroup$
    – Anders Kaseorg
    Jan 8 at 1:51










  • $begingroup$
    The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
    $endgroup$
    – Math Enthusiast
    Jan 13 at 22:14






  • 1




    $begingroup$
    @MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
    $endgroup$
    – Anders Kaseorg
    Jan 13 at 22:42










  • $begingroup$
    Ok thanks :) I thought you didn't see it sorry
    $endgroup$
    – Math Enthusiast
    Jan 15 at 1:11
















$begingroup$
This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
$endgroup$
– Math Enthusiast
Jan 8 at 0:32




$begingroup$
This is exactly the concise and insightful explanation I hoped to find! Thank you :) Could elaborate just a bit more on why this proves that every arrow in the grid must be used exactly once? I am almost but not quite understanding
$endgroup$
– Math Enthusiast
Jan 8 at 0:32




1




1




$begingroup$
You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
$endgroup$
– Anders Kaseorg
Jan 8 at 1:51




$begingroup$
You can see that each arrow is used exactly once in the black and white grid, just by applying the substitution rule and seeing what happens. All we’ve done to get from the black and white grid to the colored picture is recolor some arrows. Does this make sense? Which part are you stuck on?
$endgroup$
– Anders Kaseorg
Jan 8 at 1:51












$begingroup$
The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
$endgroup$
– Math Enthusiast
Jan 13 at 22:14




$begingroup$
The part I was stuck on was seeing why every arrow in the grid ends up colored (why we don't ever "miss" an arrow as the curves grow). I think that I understand now that this is because all four arrows in the starting position form a complete, bijective coloring of the interior of the initial 2x2 unit square. Because of the scaling action of our iterative process, this square grows to be infinitely large while retaining its complete (interior) coloring? Thanks for bearing with me – Math Enthusiast Jan 8 at 6:30
$endgroup$
– Math Enthusiast
Jan 13 at 22:14




1




1




$begingroup$
@MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
$endgroup$
– Anders Kaseorg
Jan 13 at 22:42




$begingroup$
@MathEnthusiast Yeah…is that a question? I drew these pictures at the same scale, with the individual arrows getting smaller rather than the initial square getting bigger, but I suppose you could think of them either way.
$endgroup$
– Anders Kaseorg
Jan 13 at 22:42












$begingroup$
Ok thanks :) I thought you didn't see it sorry
$endgroup$
– Math Enthusiast
Jan 15 at 1:11




$begingroup$
Ok thanks :) I thought you didn't see it sorry
$endgroup$
– Math Enthusiast
Jan 15 at 1:11


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics 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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064350%2ffour-dragon-curves-are-edge-covering-plane-tiling%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

Bressuire

Cabo Verde

Gyllenstierna