faster than O(n^4) algorithm for solving the following problem
$begingroup$
This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing.
Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there exists x, y and z in Q that satisfy all the inequalities.
Here is an O(n4) algorithm for solving this: for each triple of inequalities, intersect their corresponding planes to get a point (x,y,z) iff possible. If no such intersecting point exists continue on to the next triple of inequalities. Test each of these intersection points against all the inequalities. If a particular point satisfies all the inequalities the solution has been found. If none of these points satisfy all the inequalities then there is no point satisfying the system of inequalities. There are O(n3) such intersection points and there are n inequalities thus the algorithm is O(n4).
I would like a faster algorithm for solving this (eg: O(n3), O(n2), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. You may notice this problem is a subset of the more general k-dimensional problem where there are points in k-dimensions instead of 3 dimensions as in this problem or 2 dimensions as in my previous problem mentioned above. The time complexity of my algorithm generalized to k dimensions is O(nk+1). Ideally I would like something that is a polynomial time algorithm however any improvements over my naive algorithm would be great. Thanks
geometry algorithms computational-complexity
asked Dec 11 '18 at 6:00
mathewmathew
437215
$endgroup$
add a comment |
$begingroup$
This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing.
Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there exists x, y and z in Q that satisfy all the inequalities.
Here is an O(n4) algorithm for solving this: for each triple of inequalities, intersect their corresponding planes to get a point (x,y,z) iff possible. If no such intersecting point exists continue on to the next triple of inequalities. Test each of these intersection points against all the inequalities. If a particular point satisfies all the inequalities the solution has been found. If none of these points satisfy all the inequalities then there is no point satisfying the system of inequalities. There are O(n3) such intersection points and there are n inequalities thus the algorithm is O(n4).
I would like a faster algorithm for solving this (eg: O(n3), O(n2), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. You may notice this problem is a subset of the more general k-dimensional problem where there are points in k-dimensions instead of 3 dimensions as in this problem or 2 dimensions as in my previous problem mentioned above. The time complexity of my algorithm generalized to k dimensions is O(nk+1). Ideally I would like something that is a polynomial time algorithm however any improvements over my naive algorithm would be great. Thanks
geometry algorithms computational-complexity
asked Dec 11 '18 at 6:00
mathewmathew
437215
$endgroup$
$begingroup$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27
add a comment |
$begingroup$
This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing.
Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there exists x, y and z in Q that satisfy all the inequalities.
Here is an O(n4) algorithm for solving this: for each triple of inequalities, intersect their corresponding planes to get a point (x,y,z) iff possible. If no such intersecting point exists continue on to the next triple of inequalities. Test each of these intersection points against all the inequalities. If a particular point satisfies all the inequalities the solution has been found. If none of these points satisfy all the inequalities then there is no point satisfying the system of inequalities. There are O(n3) such intersection points and there are n inequalities thus the algorithm is O(n4).
I would like a faster algorithm for solving this (eg: O(n3), O(n2), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. You may notice this problem is a subset of the more general k-dimensional problem where there are points in k-dimensions instead of 3 dimensions as in this problem or 2 dimensions as in my previous problem mentioned above. The time complexity of my algorithm generalized to k dimensions is O(nk+1). Ideally I would like something that is a polynomial time algorithm however any improvements over my naive algorithm would be great. Thanks
geometry algorithms computational-complexity
asked Dec 11 '18 at 6:00
mathewmathew
437215
$endgroup$
This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing.
Given a set of n inequalities each of the form ax+by+cz≤d for some a,b,c,d in Q, determine if there exists x, y and z in Q that satisfy all the inequalities.
Here is an O(n4) algorithm for solving this: for each triple of inequalities, intersect their corresponding planes to get a point (x,y,z) iff possible. If no such intersecting point exists continue on to the next triple of inequalities. Test each of these intersection points against all the inequalities. If a particular point satisfies all the inequalities the solution has been found. If none of these points satisfy all the inequalities then there is no point satisfying the system of inequalities. There are O(n3) such intersection points and there are n inequalities thus the algorithm is O(n4).
I would like a faster algorithm for solving this (eg: O(n3), O(n2), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. You may notice this problem is a subset of the more general k-dimensional problem where there are points in k-dimensions instead of 3 dimensions as in this problem or 2 dimensions as in my previous problem mentioned above. The time complexity of my algorithm generalized to k dimensions is O(nk+1). Ideally I would like something that is a polynomial time algorithm however any improvements over my naive algorithm would be great. Thanks
geometry algorithms computational-complexity
geometry algorithms computational-complexity
asked Dec 11 '18 at 6:00
mathewmathew
437215
asked Dec 11 '18 at 6:00
mathewmathew
437215
asked Dec 11 '18 at 6:00
mathewmathew
437215
asked Dec 11 '18 at 6:00
mathewmathew
437215
asked Dec 11 '18 at 6:00
mathewmathew
437215
437215
$begingroup$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27
add a comment |
$begingroup$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27
$begingroup$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You can modify your algorithm a bit to make it $O(n^3)$.
If we have a line, we can check if there's a point on that line satisfying all inequalities in $O(n)$ time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes ($O(n^2)$ of them. So you get a total complexity of $O(n^3)$.
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
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%2f3034948%2ffaster-than-on4-algorithm-for-solving-the-following-problem%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$
You can modify your algorithm a bit to make it $O(n^3)$.
If we have a line, we can check if there's a point on that line satisfying all inequalities in $O(n)$ time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes ($O(n^2)$ of them. So you get a total complexity of $O(n^3)$.
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
add a comment |
$begingroup$
You can modify your algorithm a bit to make it $O(n^3)$.
If we have a line, we can check if there's a point on that line satisfying all inequalities in $O(n)$ time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes ($O(n^2)$ of them. So you get a total complexity of $O(n^3)$.
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
add a comment |
$begingroup$
You can modify your algorithm a bit to make it $O(n^3)$.
If we have a line, we can check if there's a point on that line satisfying all inequalities in $O(n)$ time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes ($O(n^2)$ of them. So you get a total complexity of $O(n^3)$.
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
$endgroup$
You can modify your algorithm a bit to make it $O(n^3)$.
If we have a line, we can check if there's a point on that line satisfying all inequalities in $O(n)$ time. If we denote one of the directions on this line "up", each plane gives you an upper or lower bound on the part of the line satisfying the inequalities. So we can compute the intersection points between the line and each plane, and check if the lowest upper bound is above the highest lower bound.
Like in your algorithm, candidate lines can be intersection lines between each pair of planes ($O(n^2)$ of them. So you get a total complexity of $O(n^3)$.
Note, care must be taken for the special case when all planes are parallel and so there's no intersection lines.
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
answered Dec 11 '18 at 19:36
Todor MarkovTodor Markov
2,420412
2,420412
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
add a comment |
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
$begingroup$
Thank you for this, if no better solutions are put forward I'll accept your answer however I'm still hoping a polynomial time algorithm will be found.
$endgroup$
– mathew
Dec 12 '18 at 9:06
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%2f3034948%2ffaster-than-on4-algorithm-for-solving-the-following-problem%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$
In practice, the simplex method will usually work quickly.
$endgroup$
– Greg Martin
Dec 11 '18 at 6:27
$begingroup$
Note that you can actually have a feasible region that contains no intersection points of three planes. It could, for example, be an infinite prism stretching both ways.
$endgroup$
– Todor Markov
Dec 11 '18 at 19:27