Four Dragon Curves are Edge-covering/Plane-tiling
$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).
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
$endgroup$
add a comment |
$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).
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
$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
add a comment |
$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).
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
$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).
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
fractals tiling
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
add a comment |
$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
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.
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.
Now we can color four arrows of the initial grid and watch them grow into four dragons:
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.
$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
add a comment |
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
});
}
});
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%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
$begingroup$
Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.
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.
Now we can color four arrows of the initial grid and watch them grow into four dragons:
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.
$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
add a comment |
$begingroup$
Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.
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.
Now we can color four arrows of the initial grid and watch them grow into four dragons:
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.
$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
add a comment |
$begingroup$
Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.
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.
Now we can color four arrows of the initial grid and watch them grow into four dragons:
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.
$endgroup$
Here’s the substitution rule that generates the dragon curve. It replaces each arrow with two smaller rotated arrows with particular orientations.
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.
Now we can color four arrows of the initial grid and watch them grow into four dragons:
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.
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
add a comment |
$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
add a comment |
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.
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%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
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$
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