How do I find a point/points that is/are at most a certain distance (i.e. 30 km) away from 4 points?

Question

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!

Answer 1

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\ & \displaystyle\frac{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.}\ & \displaystyle\sum_{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.