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

In summary, the conversation discusses the problem of determining the existence of a point or set of points within a certain distance from a fixed set of points. The speaker suggests that this problem is isomorphic to determining if N circles of radius k overlap in a common region. They also propose a solution for this problem, involving the maximum Euclidean distance between any two points in the set, and suggest that this solution can be extended to any number of dimensions. The speaker also mentions the potential for a more efficient algorithm and asks for feedback on their ideas.
  • #1
ellipsis
158
24
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.
 
Mathematics news on Phys.org
  • #2
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.
 
  • #3
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.
 
Last edited:
  • #4
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.
 
Last edited:

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

1. What is the definition of a point?

A point is a location in space that has no size, shape, or dimension. It is represented by a dot and is the most basic element in geometry and mathematics.

2. How is distance measured between two points?

Distance between two points can be measured using various methods, such as the Pythagorean theorem, the distance formula, or using a ruler or measuring tape.

3. How is the existence of points within a certain distance from fixed points determined?

The existence of points within a certain distance from fixed points can be determined by calculating the distance between the points and comparing it to the given distance. If the calculated distance is less than or equal to the given distance, then the point exists within the specified distance from the fixed point.

4. Are there any real-life applications for the concept of points within a certain distance from fixed points?

Yes, this concept is widely used in various fields such as engineering, navigation, and computer science. For example, in GPS navigation, the distance between the user's current location and the destination point is calculated to determine the shortest route.

5. Can there be multiple points within a given distance from a fixed point?

Yes, there can be multiple points within a given distance from a fixed point. The number of points depends on the size of the distance and the positioning of the fixed point. For example, there can be infinitely many points within a given distance from a fixed point on a line segment.

Similar threads

Replies
4
Views
805
Replies
13
Views
1K
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
Replies
4
Views
894
  • General Math
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
20
Views
2K
  • General Math
Replies
8
Views
1K
Back
Top