4 Points with 2 different colors and 2 Lines partitioning the plane - Combinatorial geometry algorithm...
$begingroup$
We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two points ($p_i$) are Red and the second two points ($p'_i$) are blue. We want to find two equation of lines ($y = a x + b$ and $y = a' x + b'$) such that if we graph them on x-y planes, they partition the plane in a way that no points with different colors get in the same partition. (The picture below is a valid diagram that satisfies the conditions - different colors are different shapes (cross and circle) in this picture)
Now I want to find an algorithm that finds at least one $a$ and $b$ and $a'$ and $b'$ such that they satisfy the problem statements. The question statements also mentioned that in very rare conditions, there is maybe no answer to the problem so we must also make sure it has at least one answer.
The question is actually a programming problem but I think the main part of the question is a combinatorial geometry math problem and programming it with knowing the answer is not difficult. So I asked it here. I really don't know how to approach these type of questions where a lot of different conditions may happen. And absolutely we can't check a lot of different $a , b , a' ,b '$ even with a powerful computer. We want an algorithm that find these perhaps by doing some math -and logical checks- on the coordinates.
It is also said that all ($x_i , y_i,x'_i , y'_i , a , b , a' ,b'$)are integers. And in special conditions, the line can be$ x= c'$ , $x =c'$ (not in the usual $y = ax + b$ form)
Sorry for my English. If the question isn't clear enough, ask the problem so I may clarify it.
combinatorics algorithms combinatorial-geometry
asked Dec 4 '18 at 23:14
amir naamir na
625
$endgroup$
add a comment |
$begingroup$
We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two points ($p_i$) are Red and the second two points ($p'_i$) are blue. We want to find two equation of lines ($y = a x + b$ and $y = a' x + b'$) such that if we graph them on x-y planes, they partition the plane in a way that no points with different colors get in the same partition. (The picture below is a valid diagram that satisfies the conditions - different colors are different shapes (cross and circle) in this picture)
Now I want to find an algorithm that finds at least one $a$ and $b$ and $a'$ and $b'$ such that they satisfy the problem statements. The question statements also mentioned that in very rare conditions, there is maybe no answer to the problem so we must also make sure it has at least one answer.
The question is actually a programming problem but I think the main part of the question is a combinatorial geometry math problem and programming it with knowing the answer is not difficult. So I asked it here. I really don't know how to approach these type of questions where a lot of different conditions may happen. And absolutely we can't check a lot of different $a , b , a' ,b '$ even with a powerful computer. We want an algorithm that find these perhaps by doing some math -and logical checks- on the coordinates.
It is also said that all ($x_i , y_i,x'_i , y'_i , a , b , a' ,b'$)are integers. And in special conditions, the line can be$ x= c'$ , $x =c'$ (not in the usual $y = ax + b$ form)
Sorry for my English. If the question isn't clear enough, ask the problem so I may clarify it.
combinatorics algorithms combinatorial-geometry
asked Dec 4 '18 at 23:14
amir naamir na
625
$endgroup$
add a comment |
$begingroup$
We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two points ($p_i$) are Red and the second two points ($p'_i$) are blue. We want to find two equation of lines ($y = a x + b$ and $y = a' x + b'$) such that if we graph them on x-y planes, they partition the plane in a way that no points with different colors get in the same partition. (The picture below is a valid diagram that satisfies the conditions - different colors are different shapes (cross and circle) in this picture)
Now I want to find an algorithm that finds at least one $a$ and $b$ and $a'$ and $b'$ such that they satisfy the problem statements. The question statements also mentioned that in very rare conditions, there is maybe no answer to the problem so we must also make sure it has at least one answer.
The question is actually a programming problem but I think the main part of the question is a combinatorial geometry math problem and programming it with knowing the answer is not difficult. So I asked it here. I really don't know how to approach these type of questions where a lot of different conditions may happen. And absolutely we can't check a lot of different $a , b , a' ,b '$ even with a powerful computer. We want an algorithm that find these perhaps by doing some math -and logical checks- on the coordinates.
It is also said that all ($x_i , y_i,x'_i , y'_i , a , b , a' ,b'$)are integers. And in special conditions, the line can be$ x= c'$ , $x =c'$ (not in the usual $y = ax + b$ form)
Sorry for my English. If the question isn't clear enough, ask the problem so I may clarify it.
combinatorics algorithms combinatorial-geometry
asked Dec 4 '18 at 23:14
amir naamir na
625
$endgroup$
We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two points ($p_i$) are Red and the second two points ($p'_i$) are blue. We want to find two equation of lines ($y = a x + b$ and $y = a' x + b'$) such that if we graph them on x-y planes, they partition the plane in a way that no points with different colors get in the same partition. (The picture below is a valid diagram that satisfies the conditions - different colors are different shapes (cross and circle) in this picture)
Now I want to find an algorithm that finds at least one $a$ and $b$ and $a'$ and $b'$ such that they satisfy the problem statements. The question statements also mentioned that in very rare conditions, there is maybe no answer to the problem so we must also make sure it has at least one answer.
The question is actually a programming problem but I think the main part of the question is a combinatorial geometry math problem and programming it with knowing the answer is not difficult. So I asked it here. I really don't know how to approach these type of questions where a lot of different conditions may happen. And absolutely we can't check a lot of different $a , b , a' ,b '$ even with a powerful computer. We want an algorithm that find these perhaps by doing some math -and logical checks- on the coordinates.
It is also said that all ($x_i , y_i,x'_i , y'_i , a , b , a' ,b'$)are integers. And in special conditions, the line can be$ x= c'$ , $x =c'$ (not in the usual $y = ax + b$ form)
Sorry for my English. If the question isn't clear enough, ask the problem so I may clarify it.
combinatorics algorithms combinatorial-geometry
combinatorics algorithms combinatorial-geometry
asked Dec 4 '18 at 23:14
amir naamir na
625
asked Dec 4 '18 at 23:14
amir naamir na
625
edited Dec 5 '18 at 14:28
amir na
asked Dec 4 '18 at 23:14
amir naamir na
625
asked Dec 4 '18 at 23:14
amir naamir na
625
asked Dec 4 '18 at 23:14
amir naamir na
625
625
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Calculate the line running through two points of the same colour. If the other two points are on one side you can simply shift this line a bit and you have finished.
In case that this is does not hold you can consider their respective distances to the line and put in intermediate lines in the margin.
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
$endgroup$
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
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%2f3026327%2f4-points-with-2-different-colors-and-2-lines-partitioning-the-plane-combinator%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$
Calculate the line running through two points of the same colour. If the other two points are on one side you can simply shift this line a bit and you have finished.
In case that this is does not hold you can consider their respective distances to the line and put in intermediate lines in the margin.
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
$endgroup$
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
add a comment |
$begingroup$
Calculate the line running through two points of the same colour. If the other two points are on one side you can simply shift this line a bit and you have finished.
In case that this is does not hold you can consider their respective distances to the line and put in intermediate lines in the margin.
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
$endgroup$
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
add a comment |
$begingroup$
Calculate the line running through two points of the same colour. If the other two points are on one side you can simply shift this line a bit and you have finished.
In case that this is does not hold you can consider their respective distances to the line and put in intermediate lines in the margin.
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
$endgroup$
Calculate the line running through two points of the same colour. If the other two points are on one side you can simply shift this line a bit and you have finished.
In case that this is does not hold you can consider their respective distances to the line and put in intermediate lines in the margin.
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
answered Dec 5 '18 at 0:56
sehiglesehigle
1565
1565
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
add a comment |
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
$begingroup$
Use the normal form of the line and everything you need to do is evaluating.
$endgroup$
– sehigle
Dec 5 '18 at 1:02
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%2f3026327%2f4-points-with-2-different-colors-and-2-lines-partitioning-the-plane-combinator%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
