10
$\begingroup$

Important: I'm now convinced that 4 points are needes in order to reduce the solutions to a finite number. (Which is necessary because I need ALL solutions)

In a computer science context I need to solve a geometrical problem which states:

Given three points in three-dimensional space, find a line $L$ (in any form, e.g. specify two points which lie on the line) so that the distance between each of the points and $L$ are equal to a given distance $d$, if possible.

By distance between a point $P$ and a line $L$, the euclidean distance between $P$ and the foot of the perpendicular on $L$ that passes through $P$ is meant.

In two dimensions (given two points) this is rather simple as it involves only a few trigonometric functions, altough I really struggle with it in three dimensions. The reason surely is that I'm not from a math background and don't know too much about linear algebra (which I believe is involved here).

It would be ideal if there is a solution for $N$ dimensions (I think that $N$ Points are needed then), altough I would be very happy if someone could give at least some hints about the three dimensional problem (maybe some sort of heuristic that i didn't thought of could also work). :)

EDIT: Clarification

The distance between the points and the line is a given constant. Example: Given three Points and a distance $d=3$, I want to find the line which has a distance of $d$ (in this case $3$) to every given point, if possible (of course there are many cases where such a line does not exist). And I am aware of the fact that this line is not unique (several, or in case of colinearity of the three points, infinitely many lines exist)

EDIT: Clarification II

It seems that my wording causes much confusion about exactly WHAT properties the line should have. A picture showing the two-dimensional case follows:

In this case the Points $P_1$ and $P_2$ are given and the task was to find the line $g$ such that every given Point has the same shortest distance $r_B$ (which is preset) to $g$. (In this context the line was specified by a point $C$ and the angle $\alpha$, altough I'm happy with any kind of parameterization).

Now I have given 3 three-dimensional points and want to find a line with the described properties and I do not have any idea how to do this.

EDIT III:

I should also have mentioned that I should be able to find all solutions (I am 99% convinced that there is only a finite number of solutions for ordinary cases)

$\endgroup$
10
  • $\begingroup$ Just to clarify by distance of point from line you mean the minimal distance right? $\endgroup$
    – DRF
    Commented Apr 15, 2015 at 15:46
  • 1
    $\begingroup$ Yes, like I explained. I mean the minimal distance (which is the general undestanding of "distance line-point" anyway). $\endgroup$
    – thegentlecat
    Commented Apr 15, 2015 at 15:47
  • 2
    $\begingroup$ Equivalently, you are looking for the line(s) tangent to three spheres of radius $d$ centered at the three given points. $\endgroup$
    – user856
    Commented Apr 15, 2015 at 19:03
  • 1
    $\begingroup$ I don't have time to write up an actual answer, but I think a useful insight here is to consider the case of only 2 points in 3 dimensions. In that case, all of the possible solutions form a family of hyperboloids of revolution (where the axis of revolution coincides with the 2 points). To find the solution for 3 points you want to know where these hyperboloids are tangent to a third sphere. $\endgroup$
    – Kyle
    Commented Apr 15, 2015 at 19:50
  • 1
    $\begingroup$ Another thought I had was that every solution line can be associated with an orthogonal plane. If everything is projected into that plane, then the line becomes a single point which is equidistant from the projections of the 3 original points. Since 3 points in 2D is sufficient to define a circle, we want to find all planes where the projected points all lie on a circle of radius d. I don't see that making anything necessarily easier, but it's something else to consider. $\endgroup$
    – Kyle
    Commented Apr 15, 2015 at 21:53

5 Answers 5

Reset to default
6
$\begingroup$

Maybe the following will help. It's not an answer, but it's too long for a comment.

Suppose the given distance is $d$. Then $L$ must be simultaneously tangent to three spheres of radius $d$, one centered at each of the given points.

Consider the case where the distances between some pair of the points is $D>2d$. The radius $d$ spheres can be nestled inside a ruled surface of this shape (so long as it's sized appropriately):

enter image description here

Any line of the ruled surface is tangent to both spheres.

You can also fit two spheres with centers distance $D$ apart into a ruled surface that's more (or completely) cone-like, or into one that's less cone-like and more (or exactly) cylindrical. Any of these ruled surfaces will yield an infinite number of lines $L$ tangent to these first two spheres.

If the sphere of radius $d$ about the third point intersects any of these ruled surfaces (hyperboloids of one sheet with axis containing the first two spheres' centers - the cone and the cylinder being degenerate ones), it seems like there will be either one or two lines $L$ from that ruled surface where $L$ equidistant from the three points.

I think that the third sphere will intersect one of these ruled surfaces if and only if it intersects either the cone or the cylinder, so maybe only the degenerate hyperboloids need to be considered.

If none of the points are more than $2d$ units apart, the first two spheres will intersect in a circle. The families of lines tangent to both will comprise a cylinder and some hyperboloids, but you can't twist them completely into a cone. Instead, there will be a different degenerate ruled family of tangent lines: those in the plane through the spheres' circle of intersection that are also tangent to that circle. Again, if the third sphere intersects any of these families of lines (and I think in this case it must), you'll get solutions.

$\endgroup$
5
  • $\begingroup$ These are very good thoughts. Altough I don't think that the third sphere has to intersect the cone or the cylinder, because that would mean that the line has to lie on a plane with the first two points and this is obviously not the general case for every possible solution (e.g. an equilateral triangle has solutions where this holds true, but think about the solution that goes through the circumcenter of it; there isn't any common plane between the line and two of the three points). $\endgroup$
    – thegentlecat
    Commented Apr 15, 2015 at 22:30
  • $\begingroup$ @thegentlecat If the third sphere doesn't intersect any of the hyperboloid surfaces, there is no solution, since the hyperboloid surfaces are the set of solutions for 2 points. The set of solutions for 3 points must be a subset of these, so the third sphere must intersect the surfaces in order to have a solution. $\endgroup$
    – Kyle
    Commented Apr 16, 2015 at 2:20
  • $\begingroup$ @thegentlecat: I’m not sure I completely understand your comment, but what I meant is that in the $D>2d$ case, if the third sphere intersects any of the hyperboloids, I think it necessarily also intersects either the cone or the cylinder. In other words, if there’s a line $L$ that solves the problem, there is also a line $L'$ that solves that problem that is on the cylinder or cone (and is then coplanar with the first two points). As you point out, there are solutions $L$ for the corners of an equilateral triangle that are not coplanar with any two points, but there are solutions that are. $\endgroup$
    – Steve Kass
    Commented Apr 16, 2015 at 2:22
  • $\begingroup$ Yes, there are solutions where this is true, but I need all possible solutions and I thought about it and am convinced that the number of solutions is infinite given three points; four are needed instead to reduce the solutions to a finite number. (I updated the question) $\endgroup$
    – thegentlecat
    Commented Apr 16, 2015 at 5:33
  • $\begingroup$ According to this research paper, four unit spheres have in general at most 12 common tangent lines (but infinitely many if the centers are aligned). loria.fr/~lazard/paper/4balls.pdf $\endgroup$
    – Steve Kass
    Commented Apr 16, 2015 at 18:03
5
$\begingroup$

Let me briefly explain the case of $3$ dimension:

Find the plane contains those $3$ points. In this plane, find the circumcenter of the triangle formed by these $3$ points, then the straight line perpendicular to this plane and passing through the circumcenter is the required line.

$\endgroup$
7
  • 3
    $\begingroup$ Thanks for your answer, but I need the Line that has a distance which is given, e.g. I have given some 3 Points and a distance $d=2$ and I want to find the Line that has a distance of $d=2$ to any of the 3 points (as long as this is possible, of course there are many cases in which such a line does not exist). $\endgroup$
    – thegentlecat
    Commented Apr 15, 2015 at 15:32
  • 2
    $\begingroup$ @Salomo that is not true actually. Think of the points $(0,0,0)$,$(4,1,0)$ and $(0,2,0)$ and $d=2$ then the line through the points $(2,0,0)$, and $(2,1,0)$ satisfies the OP's request but is not of the type you propose. $\endgroup$
    – DRF
    Commented Apr 15, 2015 at 16:10
  • 1
    $\begingroup$ I can give a counterexample: Given the distance $d=2$ three points $A$, $B$ and $C$ in 3D-space that form a equilateral triangle with sides of length $4$, your solution would conclude with the fact that such a line does not exist (because the circumcircle you described of the three points is $\frac{4}{\sqrt{3}}$). But there exists several lines: every line which passes through one of the midpoints of the triangle sides and is rotated towards the third point in such a way that it has the required angle (and this angle exists because the rotation is continuous and $\frac{4}{\sqrt{3}}>d>0$). $\endgroup$
    – thegentlecat
    Commented Apr 15, 2015 at 16:22
  • 3
    $\begingroup$ This is not an answer to the question asked (that specified the distance). The solution is certainly not unique in general. An extreme case is that the three given points are collinear. Then you can specify $d$, form a cylinder with that line as its axis and radius of the cross section $=d$. Then any line on the cylinder parallel to the axis will work, as its distance from the axis, and hence from any of the three points, is equal to $d$. $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 15, 2015 at 16:23
  • 3
    $\begingroup$ Salomo may be thinking that any point on the sought after line should be at the same distance from the three given points. This is not what the question was about. We are looking for a line such that the closest distance from that line to any of the given three points is $d$. That closest distance may be attained at different points of the line. $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 15, 2015 at 16:29
2
$\begingroup$

As you have already noted, three points is not enough in general. In most case, you will need four points to constrain the line completely. Using Plücker coordinates makes this point obvious. For a line defined by Plücker coordinates $$p_{01},p_{02},p_{03},p_{23},p_{31},p_{12}$$ the distance $d$ between a point $(x,y,z)$ and the line satisfies $$d^2=(p_{01}+zp_{31}-yp_{12})^2+(p_{02}+xp_{12}-zp_{23})^2+(p_{03}+yp_{23}-xp_{31})^2,$$ provided that $p_{23}^2+p_{31}^2+p_{12}^2=1$. The Plücker coordinates obey $$p_{01}p_{23}+p_{02}p_{31}+p_{03}p_{12}=0$$ and you can always normalize them so that $$p_{23}^2+p_{31}^2+p_{12}^2=1.$$ The four points and the two equations above yield a system of six equations for six unknowns. It can be easily solved numerically for the given coordinates of the four points. Looking for a general analytical solution might be too onerous.

To illustrate, for $d=1$ and points $$(0,0,0), (4,0,0), (6,2,0), (9,4,1)$$ I get the following lines $$(-0.236073,0.351294,0.906014,0.91316,0.399015,0.0832224),$$ $$(0.0561098,-0.577272,0.814622,0.867865,0.431585,0.24606).$$

$\endgroup$
0
$\begingroup$

I think such line may not be unique.

Find in 3D,the plane contains those 3 points. In this plane, the three points form a triangle. Let the straight line parallel to a side, say $AB$ then moving to the third point $C$ parallel on the plane. Then it will reach a line $l_1$ where ABC has the same distance $d_0$ to it (during the movement, A,B always have the same distance to the line) . Then move the line paralelly to the direction up/down perpendicular to the plane (during the movement, A,B,C always have the same distance to the line). Stop when you have the desired distance.

Of course, if the desired $d$ is too small, you can't get a solution. And for a nice $d$, you will get several solutions depending on which side you start with.

$\endgroup$
-1
$\begingroup$

There is a line for which each point has the same distance from the three points, but that distance will depend on which point of the line it was.
There is either zero, one or two points on the line that are a distance $d$ from the three points.
Given the points $(a,b,c),(e,f,g),(h,k,m)$, and a point equidistant $(x,y,z)$, then $$(x-a)^2+(y-b)^2+(z-c)^2=d^2\\(x-e)^2+(y-f)^2+(z-g)^2=d^2\\(x-h)^2+(y-k)^2+(z-m)^2=d^2$$ Subtract the first equation from the other two $$2x(a-e)+2y(b-f)+2z(c-g)=a^2-e^2+b^2-f^2+c^2-g^2\\ 2x(a-h)+2y(b-k)+(2z(c-m)=a^2-h^2+b^2-k^2+c^2-m^2$$ This is two linear equations in three unknowns. I hope you know how to solve it; it usually gives a line.
To get a common distance $d$, feed your answer back into the first equation, and you get a quadratic in $d$, which has zero, one or two solutions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .