Simple triangulation over flat torus
$begingroup$
This is somewhat of a computational question: let me know if it is inappropriate.
I have a flat torus with sone random points marked.
I would like to compute a triangulation of said torus such that my points are the vertexes of the triangulation.
A bit of googling has not given me any results. My naive idea would be to start from the fully connected graph, and every time two edges cross, simply remove one of them. Unfortunately this looks like it's going to be quite expensive, as I have $n^2$ edges each of which can potentially intersect all of the others. I also looked into the Delauney triangulation, but I am not sure it would work on an generic torus, and moreover I have no idea on how to implement it successfully. It also seems rather overkill, since I do not need my triangulation to have any special property.
Is there a simple, greedy way to get a triangulation in non-prohibitive time?
Thank you.
computer-science triangulation
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
$endgroup$
|
show 4 more comments
$begingroup$
This is somewhat of a computational question: let me know if it is inappropriate.
I have a flat torus with sone random points marked.
I would like to compute a triangulation of said torus such that my points are the vertexes of the triangulation.
A bit of googling has not given me any results. My naive idea would be to start from the fully connected graph, and every time two edges cross, simply remove one of them. Unfortunately this looks like it's going to be quite expensive, as I have $n^2$ edges each of which can potentially intersect all of the others. I also looked into the Delauney triangulation, but I am not sure it would work on an generic torus, and moreover I have no idea on how to implement it successfully. It also seems rather overkill, since I do not need my triangulation to have any special property.
Is there a simple, greedy way to get a triangulation in non-prohibitive time?
Thank you.
computer-science triangulation
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
$endgroup$
$begingroup$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52
|
show 4 more comments
$begingroup$
This is somewhat of a computational question: let me know if it is inappropriate.
I have a flat torus with sone random points marked.
I would like to compute a triangulation of said torus such that my points are the vertexes of the triangulation.
A bit of googling has not given me any results. My naive idea would be to start from the fully connected graph, and every time two edges cross, simply remove one of them. Unfortunately this looks like it's going to be quite expensive, as I have $n^2$ edges each of which can potentially intersect all of the others. I also looked into the Delauney triangulation, but I am not sure it would work on an generic torus, and moreover I have no idea on how to implement it successfully. It also seems rather overkill, since I do not need my triangulation to have any special property.
Is there a simple, greedy way to get a triangulation in non-prohibitive time?
Thank you.
computer-science triangulation
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
$endgroup$
This is somewhat of a computational question: let me know if it is inappropriate.
I have a flat torus with sone random points marked.
I would like to compute a triangulation of said torus such that my points are the vertexes of the triangulation.
A bit of googling has not given me any results. My naive idea would be to start from the fully connected graph, and every time two edges cross, simply remove one of them. Unfortunately this looks like it's going to be quite expensive, as I have $n^2$ edges each of which can potentially intersect all of the others. I also looked into the Delauney triangulation, but I am not sure it would work on an generic torus, and moreover I have no idea on how to implement it successfully. It also seems rather overkill, since I do not need my triangulation to have any special property.
Is there a simple, greedy way to get a triangulation in non-prohibitive time?
Thank you.
computer-science triangulation
computer-science triangulation
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
asked Dec 17 '18 at 10:15
Riccardo OrlandoRiccardo Orlando
1,684518
1,684518
$begingroup$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52
|
show 4 more comments
$begingroup$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52
$begingroup$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The flat torus can be constucted by identifying the opposite sides of a square in the plane.
Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.
You can generalize this for the $n$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
$endgroup$
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
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%2f3043766%2fsimple-triangulation-over-flat-torus%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$
The flat torus can be constucted by identifying the opposite sides of a square in the plane.
Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.
You can generalize this for the $n$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
$endgroup$
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
add a comment |
$begingroup$
The flat torus can be constucted by identifying the opposite sides of a square in the plane.
Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.
You can generalize this for the $n$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
$endgroup$
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
add a comment |
$begingroup$
The flat torus can be constucted by identifying the opposite sides of a square in the plane.
Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.
You can generalize this for the $n$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
$endgroup$
The flat torus can be constucted by identifying the opposite sides of a square in the plane.
Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.
You can generalize this for the $n$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
edited Dec 17 '18 at 12:49
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
answered Dec 17 '18 at 12:43
Tsemo AristideTsemo Aristide
59.3k11445
59.3k11445
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
add a comment |
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
$begingroup$
I need my triangulation to have vertexes on specific assigned points.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:47
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%2f3043766%2fsimple-triangulation-over-flat-torus%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$
Is it really significant that we are on a torus? What would you do with the same problem on a plane?
$endgroup$
– Ivan Neretin
Dec 17 '18 at 12:11
$begingroup$
Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 12:46
$begingroup$
Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow.
$endgroup$
– David K
Dec 17 '18 at 13:30
$begingroup$
Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern.
$endgroup$
– Riccardo Orlando
Dec 17 '18 at 14:39
$begingroup$
I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon.
$endgroup$
– David K
Dec 17 '18 at 19:52