- #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.
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.