Existence of point(s) within k distance of other fixed points

[ellipsis]

How do I derive an expression or algorithm that determines the existence of a point or set of points within k distance of an N number of other fixed, given points?

In application, I expect to only need to determine that this region exists for three to five points. This is part of a greater algorithm that will iterate through a large list of points and identify "groups" following this condition. Each point is a three-vector, i.e. embedded in three dimensions.

I have identified that this is isomorphic to determining that N circles of radius k overlap a common region.

In the case of two points, the distance between them must be less than or equal to 2k, for the above condition to hold.

I may have discovered an O(n^2) solution, where n is the number of points. Naturally extending the case of two points, the distance of each pair of points must be less than 2k. But one can easily construct a case for which this condition holds, but for which there is no common region of overlap (i.e. tangential circles).

We may ask: What is the largest area of the triangle formed by three points such that there exists a point which is within k distance to all of them?

An equilateral triangle with a circumscribed radius of k seems to have maximal area, which is 3*sqrt(3)*k^2

Thus, any set of three points which has more than this area definitely does not have a common region of overlap. Likewise, any set of three points which has more than 2k distance between each point does not fit the overlap condition.

It seems these two facts lead to the conclusion: Any set of three points which form a triangular area under 3*sqrt(3)*k^2, and has a maximum side-length equal to or less than 2k, will have non-empty set of points such that each point in this set has a distance of k or less to the fixed points.

If my logic is correct, this should extend to four points in three dimensions. That is, a given set would follow the overlap condition iff each edge length was under 2k, each face area was under 2k^2, and volume was under (1/9)*sqrt(3)*k^3. This is a line, square, and regular tetrahedron respectively.

Maximum area positioning of five points would be a line, pentagon, and triangular bipyramid (see: Thomson problem)

I'm not sure about any algorithms to calculate the volume of a set of points, but it is useful that any points queried will be guaranteed to be part of a convex hull (given how I intend the greater algorithm to work).

If there is a much more efficient method, a glaring incorrectness, or even further theoretical understanding about the problem I'm not detecting, please say so.

I'll update this post with my progress.

 

[Simon Bridge]

How do I derive an expression or algorithm that determines the existence of a point or set of points within k distance of an N number of other fixed, given points?

... this is not possible as you have written it.

The best way to tell if you are thinking about this well-enough is to be more pedantic about how you describe the problem.
i.e.

Lets say you have N points $\text{P}=\{\vec p_1,\vec p_2,\cdots,\vec p_N\}$ - looking at a subset Q of P consisting of n<N of them;
... are there are any other points in P which are within distance k of all the points in Q.
... perhaps you only need to know if there are any other points in P within the volume enclosed by sphere's radius k about the points in Q?

See what I mean - you have not said where the unknown points you are trying to find come from.

 

[ellipsis]

Sorry Simon, I'm very bad at formal mathematical language i.e. set theory et. al. I'll try extreme simplicity:

Imagine you have 200 randomly-spaced dots on a piece of paper, and a coin. Find the position of the coin that covers the maximum amount of points.

The first step in an efficient algorithm is determining if a given group of points have a coin that overlaps them all.

Thanks for the response, Simon. Even if nobody can help, just making these posts has clarified my ideas.

 

[ellipsis]

Ha! I've found it! If the maximum Euclidean distance between any two vectors in the set $S$ is below or equal to $2k$, then $S$ can be enclosed by a circle of radius $k$! Therefore, there exists a point which is equal to or less than $k$ from every element in the set $S$! This is valid for vectors of any dimension!

This epiphany was found on the edge of going to sleep - if it's sleep-deprived nonsense I will recant tomorrow.