Mixing
How do I find a point/points that is/are at most a certain distance (i.e. 30 km) away from 4 points?
$begingroup$
I am trying to figure out a way to find a point or points that is/are at most a certain distance (i.e. 30km) away from 4 points that are possible surrounding the point that I am trying to find.
Instead of manually measuring the distance, I am looking for a formula or a set of them to come up with it.
Thank you in advance!
discrete-mathematics algorithms
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
$endgroup$
add a comment |
$begingroup$
I am trying to figure out a way to find a point or points that is/are at most a certain distance (i.e. 30km) away from 4 points that are possible surrounding the point that I am trying to find.
Instead of manually measuring the distance, I am looking for a formula or a set of them to come up with it.
Thank you in advance!
discrete-mathematics algorithms
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
$endgroup$
1
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
1
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15
add a comment |
$begingroup$
I am trying to figure out a way to find a point or points that is/are at most a certain distance (i.e. 30km) away from 4 points that are possible surrounding the point that I am trying to find.
Instead of manually measuring the distance, I am looking for a formula or a set of them to come up with it.
Thank you in advance!
discrete-mathematics algorithms
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
$endgroup$
I am trying to figure out a way to find a point or points that is/are at most a certain distance (i.e. 30km) away from 4 points that are possible surrounding the point that I am trying to find.
Instead of manually measuring the distance, I am looking for a formula or a set of them to come up with it.
Thank you in advance!
discrete-mathematics algorithms
discrete-mathematics algorithms
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
asked Jan 27 at 1:12
Juniper SohnJuniper Sohn
1
1
1
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
1
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15
add a comment |
1
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
1
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15
1
1
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
1
1
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As I noted in the comments, I think you can just draw four circles and see if they intersect, but hey, let's go overboard.
As noted in the comments, there seem to be two possible interpretations of your problem. Both interpretations can be solved using convex programming.
Interpretation 1: Find a point that is within a fixed distance $d$ of each of a set of $m$ points, $p_1,dots,p_m$, each living in $mathbb{R}^n$ (in your question you imply $n=2$, but hey, let's go crazy). This can be formulated as the following convex program (technically a second-order conic program, or SOCP).
$$
begin{array}{rl}
min & 0 \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
The objective function equals zero since we're only interested in finding a feasible point. In general, there can be (uncountably infinitely) many points that are feasible, and this formulation allows us to add in things to the objective function. For example, maybe we want to pick the point $x$ to be as close to $p_1$ as possible. Then our optimization problem is
$$
begin{array}{rl}
min & |x-p_1| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
Of maybe we want to minimize the average distance between $x$ and all the points $p_i$:
$$
begin{array}{rl}
min & displaystylefrac{1}{m}sum_{i=1}^m|x-p_i| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
You get the idea.
Interpretation 2: Find a point such that the total distance between the $p_i$ and $x$ is less than or equal to $d$. This is again a convex program:
$$
begin{array}{rl}
min & 0 \
text{s.t.} & displaystylesum_{i=1}^m|x-p_i|leq{d}
end{array}
$$
As before, we can change the objective function to select among the multiple optimal solutions.
Computational Results
These are very simple convex programs, and can be solved, for example, with CVXPY. Here's an example of interpretation 1, where we wish to find the point with the minimum average distance to all the other points. I'll do it in two dimensions with four circles, as the OP asks.
import cvxpy as cp
import numpy as np
def main():
d = 2
p = np.array([[1,1], [-1,1.2], [-0.5,-2], [2,-1]])
m,n = p.shape
x = cp.Variable(n)
# Minimize the average distance
objective = cp.Minimize((1/m)*cp.sum([cp.norm(x-p[i,:]) for i in range(m)]))
constraints = [cp.norm(x-p[i,:]) <= d for i in range(m)]
prob = cp.Problem(objective, constraints)
res = prob.solve(solver='SCS')
print(x.value)
Here's what the result looks like. The four points $p_i$ are in blue, with circles of radius $d=2$ around them. The solution with minimum average distance to each blue point is shown in red.
answered Jan 27 at 4:09
David M.David M.
2,068420
$endgroup$
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%2f3089010%2fhow-do-i-find-a-point-points-that-is-are-at-most-a-certain-distance-i-e-30-km%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$
As I noted in the comments, I think you can just draw four circles and see if they intersect, but hey, let's go overboard.
As noted in the comments, there seem to be two possible interpretations of your problem. Both interpretations can be solved using convex programming.
Interpretation 1: Find a point that is within a fixed distance $d$ of each of a set of $m$ points, $p_1,dots,p_m$, each living in $mathbb{R}^n$ (in your question you imply $n=2$, but hey, let's go crazy). This can be formulated as the following convex program (technically a second-order conic program, or SOCP).
$$
begin{array}{rl}
min & 0 \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
The objective function equals zero since we're only interested in finding a feasible point. In general, there can be (uncountably infinitely) many points that are feasible, and this formulation allows us to add in things to the objective function. For example, maybe we want to pick the point $x$ to be as close to $p_1$ as possible. Then our optimization problem is
$$
begin{array}{rl}
min & |x-p_1| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
Of maybe we want to minimize the average distance between $x$ and all the points $p_i$:
$$
begin{array}{rl}
min & displaystylefrac{1}{m}sum_{i=1}^m|x-p_i| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
You get the idea.
Interpretation 2: Find a point such that the total distance between the $p_i$ and $x$ is less than or equal to $d$. This is again a convex program:
$$
begin{array}{rl}
min & 0 \
text{s.t.} & displaystylesum_{i=1}^m|x-p_i|leq{d}
end{array}
$$
As before, we can change the objective function to select among the multiple optimal solutions.
Computational Results
These are very simple convex programs, and can be solved, for example, with CVXPY. Here's an example of interpretation 1, where we wish to find the point with the minimum average distance to all the other points. I'll do it in two dimensions with four circles, as the OP asks.
import cvxpy as cp
import numpy as np
def main():
d = 2
p = np.array([[1,1], [-1,1.2], [-0.5,-2], [2,-1]])
m,n = p.shape
x = cp.Variable(n)
# Minimize the average distance
objective = cp.Minimize((1/m)*cp.sum([cp.norm(x-p[i,:]) for i in range(m)]))
constraints = [cp.norm(x-p[i,:]) <= d for i in range(m)]
prob = cp.Problem(objective, constraints)
res = prob.solve(solver='SCS')
print(x.value)
Here's what the result looks like. The four points $p_i$ are in blue, with circles of radius $d=2$ around them. The solution with minimum average distance to each blue point is shown in red.
answered Jan 27 at 4:09
David M.David M.
2,068420
$endgroup$
add a comment |
$begingroup$
As I noted in the comments, I think you can just draw four circles and see if they intersect, but hey, let's go overboard.
As noted in the comments, there seem to be two possible interpretations of your problem. Both interpretations can be solved using convex programming.
Interpretation 1: Find a point that is within a fixed distance $d$ of each of a set of $m$ points, $p_1,dots,p_m$, each living in $mathbb{R}^n$ (in your question you imply $n=2$, but hey, let's go crazy). This can be formulated as the following convex program (technically a second-order conic program, or SOCP).
$$
begin{array}{rl}
min & 0 \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
The objective function equals zero since we're only interested in finding a feasible point. In general, there can be (uncountably infinitely) many points that are feasible, and this formulation allows us to add in things to the objective function. For example, maybe we want to pick the point $x$ to be as close to $p_1$ as possible. Then our optimization problem is
$$
begin{array}{rl}
min & |x-p_1| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
Of maybe we want to minimize the average distance between $x$ and all the points $p_i$:
$$
begin{array}{rl}
min & displaystylefrac{1}{m}sum_{i=1}^m|x-p_i| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
You get the idea.
Interpretation 2: Find a point such that the total distance between the $p_i$ and $x$ is less than or equal to $d$. This is again a convex program:
$$
begin{array}{rl}
min & 0 \
text{s.t.} & displaystylesum_{i=1}^m|x-p_i|leq{d}
end{array}
$$
As before, we can change the objective function to select among the multiple optimal solutions.
Computational Results
These are very simple convex programs, and can be solved, for example, with CVXPY. Here's an example of interpretation 1, where we wish to find the point with the minimum average distance to all the other points. I'll do it in two dimensions with four circles, as the OP asks.
import cvxpy as cp
import numpy as np
def main():
d = 2
p = np.array([[1,1], [-1,1.2], [-0.5,-2], [2,-1]])
m,n = p.shape
x = cp.Variable(n)
# Minimize the average distance
objective = cp.Minimize((1/m)*cp.sum([cp.norm(x-p[i,:]) for i in range(m)]))
constraints = [cp.norm(x-p[i,:]) <= d for i in range(m)]
prob = cp.Problem(objective, constraints)
res = prob.solve(solver='SCS')
print(x.value)
Here's what the result looks like. The four points $p_i$ are in blue, with circles of radius $d=2$ around them. The solution with minimum average distance to each blue point is shown in red.
answered Jan 27 at 4:09
David M.David M.
2,068420
$endgroup$
add a comment |
$begingroup$
As I noted in the comments, I think you can just draw four circles and see if they intersect, but hey, let's go overboard.
As noted in the comments, there seem to be two possible interpretations of your problem. Both interpretations can be solved using convex programming.
Interpretation 1: Find a point that is within a fixed distance $d$ of each of a set of $m$ points, $p_1,dots,p_m$, each living in $mathbb{R}^n$ (in your question you imply $n=2$, but hey, let's go crazy). This can be formulated as the following convex program (technically a second-order conic program, or SOCP).
$$
begin{array}{rl}
min & 0 \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
The objective function equals zero since we're only interested in finding a feasible point. In general, there can be (uncountably infinitely) many points that are feasible, and this formulation allows us to add in things to the objective function. For example, maybe we want to pick the point $x$ to be as close to $p_1$ as possible. Then our optimization problem is
$$
begin{array}{rl}
min & |x-p_1| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
Of maybe we want to minimize the average distance between $x$ and all the points $p_i$:
$$
begin{array}{rl}
min & displaystylefrac{1}{m}sum_{i=1}^m|x-p_i| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
You get the idea.
Interpretation 2: Find a point such that the total distance between the $p_i$ and $x$ is less than or equal to $d$. This is again a convex program:
$$
begin{array}{rl}
min & 0 \
text{s.t.} & displaystylesum_{i=1}^m|x-p_i|leq{d}
end{array}
$$
As before, we can change the objective function to select among the multiple optimal solutions.
Computational Results
These are very simple convex programs, and can be solved, for example, with CVXPY. Here's an example of interpretation 1, where we wish to find the point with the minimum average distance to all the other points. I'll do it in two dimensions with four circles, as the OP asks.
import cvxpy as cp
import numpy as np
def main():
d = 2
p = np.array([[1,1], [-1,1.2], [-0.5,-2], [2,-1]])
m,n = p.shape
x = cp.Variable(n)
# Minimize the average distance
objective = cp.Minimize((1/m)*cp.sum([cp.norm(x-p[i,:]) for i in range(m)]))
constraints = [cp.norm(x-p[i,:]) <= d for i in range(m)]
prob = cp.Problem(objective, constraints)
res = prob.solve(solver='SCS')
print(x.value)
Here's what the result looks like. The four points $p_i$ are in blue, with circles of radius $d=2$ around them. The solution with minimum average distance to each blue point is shown in red.
answered Jan 27 at 4:09
David M.David M.
2,068420
$endgroup$
As I noted in the comments, I think you can just draw four circles and see if they intersect, but hey, let's go overboard.
As noted in the comments, there seem to be two possible interpretations of your problem. Both interpretations can be solved using convex programming.
Interpretation 1: Find a point that is within a fixed distance $d$ of each of a set of $m$ points, $p_1,dots,p_m$, each living in $mathbb{R}^n$ (in your question you imply $n=2$, but hey, let's go crazy). This can be formulated as the following convex program (technically a second-order conic program, or SOCP).
$$
begin{array}{rl}
min & 0 \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
The objective function equals zero since we're only interested in finding a feasible point. In general, there can be (uncountably infinitely) many points that are feasible, and this formulation allows us to add in things to the objective function. For example, maybe we want to pick the point $x$ to be as close to $p_1$ as possible. Then our optimization problem is
$$
begin{array}{rl}
min & |x-p_1| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
Of maybe we want to minimize the average distance between $x$ and all the points $p_i$:
$$
begin{array}{rl}
min & displaystylefrac{1}{m}sum_{i=1}^m|x-p_i| \
text{s.t.} & |x-p_i|leq{d}text{ for all }i=1,dots,m
end{array}
$$
You get the idea.
Interpretation 2: Find a point such that the total distance between the $p_i$ and $x$ is less than or equal to $d$. This is again a convex program:
$$
begin{array}{rl}
min & 0 \
text{s.t.} & displaystylesum_{i=1}^m|x-p_i|leq{d}
end{array}
$$
As before, we can change the objective function to select among the multiple optimal solutions.
Computational Results
These are very simple convex programs, and can be solved, for example, with CVXPY. Here's an example of interpretation 1, where we wish to find the point with the minimum average distance to all the other points. I'll do it in two dimensions with four circles, as the OP asks.
import cvxpy as cp
import numpy as np
def main():
d = 2
p = np.array([[1,1], [-1,1.2], [-0.5,-2], [2,-1]])
m,n = p.shape
x = cp.Variable(n)
# Minimize the average distance
objective = cp.Minimize((1/m)*cp.sum([cp.norm(x-p[i,:]) for i in range(m)]))
constraints = [cp.norm(x-p[i,:]) <= d for i in range(m)]
prob = cp.Problem(objective, constraints)
res = prob.solve(solver='SCS')
print(x.value)
Here's what the result looks like. The four points $p_i$ are in blue, with circles of radius $d=2$ around them. The solution with minimum average distance to each blue point is shown in red.
answered Jan 27 at 4:09
David M.David M.
2,068420
answered Jan 27 at 4:09
David M.David M.
2,068420
answered Jan 27 at 4:09
David M.David M.
2,068420
answered Jan 27 at 4:09
David M.David M.
2,068420
2,068420
add a comment |
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%2f3089010%2fhow-do-i-find-a-point-points-that-is-are-at-most-a-certain-distance-i-e-30-km%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
1
$begingroup$
Not really mathematical but if its only four points, can you just plot the four circles and see if they all intersect?
$endgroup$
– David M.
Jan 27 at 1:14
1
$begingroup$
Do you mean 30km from each point or 30km total?
$endgroup$
– Klaus
Jan 27 at 1:15
$begingroup$
Draw 4 circles and find intersection
$endgroup$
– qwr
Jan 27 at 1:15