Cylinders Through Five Points: Complex and Real Enumerative Geometry

Abstract. It is known that five points in (ℝ^3) generically determine a finite number of cylinders containing those points. We discuss ways in which it can be shown that the generic (complex) number of solutions, with multiplicity, is six, of which an even number will be real valued and hence correspond to actual cylinders in (ℝ^3). We partially classify the case of no real solutions in terms of the geometry of the five given points. We also investigate the special case where the five given points are coplanar, as it differs from the generic case for both complex and real valued solution cardinalities.

2000 Mathematics Subject Classification: 14N10, 14Q10, 51N20, 52A15, 65C05, 65H10, 68U20.

Key words and phrases: Enumerative geometry, Gröbner bases, nonlinear systems, constraint geometry.

This is a slightly updated version of a paper that appears in: Proceedings of the Sixth International Workshop on Automated Deduction in Geometry (ADG 2006), Francisco Botana and Tomas Recio, editors. Lecture Notes in Artificial Intelligence, Springer-Verlag.

. Introduction

Given five generic points in (ℝ^3) it is not hard to show that there are finitely many solutions to the set of equations that determine cylinders containing those points. This is to be expected because cylinders have five degrees of freedom (a radius and four parameters to determine the axial line). Several papers prove that the generic number of such solutions, in complex space, is six (counted with multiplicity) [] [] [] []. Of these any even number may be real valued.

This is of importance for several reasons. First we indicate two constraint geometry interpretations of the problem.

• Given five points in (ℝ^3), find the smallest positive r and axis parameters such that the cylinder of radius 2r with those parameters tangentially encloses the balls of radius r centered at the points [] [].

• A common need in scene classification [] is to find a best fitting cylinder for a set of more than five data points. To do so one might start with an exact fit to five points, followed by optimization methods to get a best fit to the full ensemble. See [] for several references to applications of this.

In order to tackle either of these it is necessary to find all cylinders through five given points []; clearly it is useful to know the expected size of the solution set (or an upper bound, if we restrict to only real valued solutions). In this paper we discuss several aspects to this enumeration problem.

Some experimentation indicates that it is not infrequent, when working with pseudorandom point coordinates, to have configurations with no real cylinder solutions. We investigate this situation in an attempt to understand the geometry of the configurations that give rise to it. Another point of interest is the case where the five points are coplanar. In this situation we will see that the generic number of complex solutions to the cylinder parameter equations is four. It turns out, however, that the number of real solutions is at most two. In discussing the case of coplanar data we state a conjecture regarding the degenerate situation where there is a dimensional component to the cylinder solutions. This is of interest insofar as configurations near one with such a solution set might exhibit numerical instabilities in a computational setting.

The related problem of finding cylinders of a given radius through four given points in (ℝ^3) is discussed in [] [] [] []. The special case of four coplanar points is discussed in []. In contrast to cylinders through five coplanar points, all cylinder solutions of given radius through four coplanar points can be real valued.

This paper is a companion to []. Substantial emphasis therein was placed on various aspects of solving systems and related computation for purposes of deducing properties of cylinders through five points. Here we rely primarily on elementary arguments that cover the theory, with less focus on computational specifics. Experiments that gave rise to this use code similar to that presented and explained in []. The rest of this paper is as follows. Section 2 proves that there are generically six (possibly complex valued) solutions to the equations for cylinders containing five given points. We begin by formulating polynomial conditions that the fourth and fifth points project to the same circle as the first three in a given direction, and work with the ideal formed by these polynomials. The main tactic is a count of solutions in projective space, followed by a simple computation to enumerate solutions at infinity. We then cover some implications of this. Section 3 discusses in detail the case of no real solutions. Here the main tool is again the cocircularity polynomials; we now make observations about the behavior of their respective direction curves in real space. In section 4 we look at cases that have six real solutions. Section 5 investigates the special case when the points are coplanar. This is followed with a summary and some directions of further inquiry.

One way to approach some of these problems, from the perspective of automated geometry, is to employ comprehensive Gröbner systems as in [], to classify both generic solutions and specialized configurations e.g. where the number of solutions becomes infinite. The difficulty is that, to date, the computations involved have been intractable. One could regard the alternate approach taken in this paper as a blend of computational tools and human guidance, to make progress on problems for which fully automated methods seem to falter. That is to say, we do not work with full-blown automated geometric deduction tools, but borrow a bit from underlying computational methods.

In the sequel we use "cylinder" to denote solutions to polynomial equations for a cylinder, regardless of whether they are real or complex valued. To specify the former we use "real cylinders". Typically we will use the term "parameters" to refer to coordinates in the configuration space of the five points (which we may identify with (ℝ^15) or even (ℂ^15)). The values that specify a cylinder, to wit, radius and axial line features, are generally referred to as "variables" (since they are what we solve for in finding cylinders) or as "cylinder parameters" to distinguish them from the coordinate parameters already mentioned.

I thank the anonymous referees of this and a prior draft. Their several useful remarks and suggestions improved both exposition and references.

. Counting (Possibly Complex) Cylinders Through Five Points

We recall a way of setting up the problem that gives rise to two equations in two unknowns. This specific formulation is used in [] but similar methods are given in [] []. We place one point at the origin, another at (1,0,0), and a third in the x y coordinate plane at ((Subscript[x, 2]),(Subscript[y, 2]),0). We project these onto the set of planes through the origin parametrized by normal vector (a,b,1). In each such projection they uniquely determine a (possibly degenerate) circle. We obtain the two polynomials below by enforcing that the two remaining points, ((Subscript[x, 3]),(Subscript[y, 3]),(Subscript[z, 3])) and ((Subscript[x, 4]),(Subscript[y, 4]),(Subscript[z, 4])), project onto the same circle.

(-(Subscript[x, 3]) (Subscript[y, 2])-(b^2) (Subscript[x, 3]) (Subscript[y, 2])+(Subscript[x, 3]^2) (Subscript[y, 2])+(b^2) (Subscript[x, 3]^2) (Subscript[y, 2])+(Subscript[x, 2]) (Subscript[y, 3])+(b^2) (Subscript[x, 2]) (Subscript[y, 3])-(Subscript[x, 2]^2) (Subscript[y, 3])-(b^2) (Subscript[x, 2]^2) (Subscript[y, 3])+2 a b (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[y, 3])-2 a b (Subscript[x, 3]) (Subscript[y, 2]) (Subscript[y, 3])-(Subscript[y, 2]^2) (Subscript[y, 3])-(a^2) (Subscript[y, 2]^2) (Subscript[y, 3])+(Subscript[y, 2]) (Subscript[y, 3]^2)+(a^2) (Subscript[y, 2]) (Subscript[y, 3]^2)-b (Subscript[x, 2]) (Subscript[z, 3])-(b^3) (Subscript[x, 2]) (Subscript[z, 3])+b (Subscript[x, 2]^2) (Subscript[z, 3])+(b^3) (Subscript[x, 2]^2) (Subscript[z, 3])+a (Subscript[y, 2]) (Subscript[z, 3])+a (b^2) (Subscript[y, 2]) (Subscript[z, 3])-2 a (b^2) (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[z, 3])-2 a (Subscript[x, 3]) (Subscript[y, 2]) (Subscript[z, 3])+b (Subscript[y, 2]^2) (Subscript[z, 3])+(a^2) b (Subscript[y, 2]^2) (Subscript[z, 3])-2 b (Subscript[y, 2]) (Subscript[y, 3]) (Subscript[z, 3])+(a^2) (Subscript[y, 2]) (Subscript[z, 3]^2)+(b^2) (Subscript[y, 2]) (Subscript[z, 3]^2),-(Subscript[x, 4]) (Subscript[y, 2])-(b^2) (Subscript[x, 4]) (Subscript[y, 2])+(Subscript[x, 4]^2) (Subscript[y, 2])+(b^2) (Subscript[x, 4]^2) (Subscript[y, 2])+(Subscript[x, 2]) (Subscript[y, 4])+(b^2) (Subscript[x, 2]) (Subscript[y, 4])-(Subscript[x, 2]^2) (Subscript[y, 4])-(b^2) (Subscript[x, 2]^2) (Subscript[y, 4])+2 a b (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[y, 4])-2 a b (Subscript[x, 4]) (Subscript[y, 2]) (Subscript[y, 4])-(Subscript[y, 2]^2) (Subscript[y, 4])-(a^2) (Subscript[y, 2]^2) (Subscript[y, 4])+(Subscript[y, 2]) (Subscript[y, 4]^2)+(a^2) (Subscript[y, 2]) (Subscript[y, 4]^2)-b (Subscript[x, 2]) (Subscript[z, 4])-(b^3) (Subscript[x, 2]) (Subscript[z, 4])+b (Subscript[x, 2]^2) (Subscript[z, 4])+(b^3) (Subscript[x, 2]^2) (Subscript[z, 4])+a (Subscript[y, 2]) (Subscript[z, 4])+a (b^2) (Subscript[y, 2]) (Subscript[z, 4])-2 a (b^2) (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[z, 4])-2 a (Subscript[x, 4]) (Subscript[y, 2]) (Subscript[z, 4])+b (Subscript[y, 2]^2) (Subscript[z, 4])+(a^2) b (Subscript[y, 2]^2) (Subscript[z, 4])-2 b (Subscript[y, 2]) (Subscript[y, 4]) (Subscript[z, 4])+(a^2) (Subscript[y, 2]) (Subscript[z, 4]^2)+(b^2) (Subscript[y, 2]) (Subscript[z, 4]^2))

One observes from this that the number of solutions is generically finite, and by Bezout's theorem it is moreover bounded by nine, as each polynomial has total degree of three in the variables (a,b). Moreover, using, say pseudorandom values for the coordinate parameters and solving for the cylinder parameters as per [] or [] one obtains six solutions. Thus we know there are generically at least that many solutions.

Before developing the theory it might be instructive to see how these curves intersect real space. We work with an explicit set of points: (0, 0, 0), (1, 0, 0), (5/3, 3/4, 0), (5/4,1, 4/5), (3/4, 1/3, 1/2). Plugging these parameters into the polynomials above gives

(-9925-12960 a+9612 (a^2)+2000 b+9000 a b+6480 (a^2) b-5713 (b^2)-20160 a (b^2)+12800 (b^3),-1063-324 a+144 (a^2)+1014 b+792 a b+486 (a^2) b-559 (b^2)-1512 a (b^2)+960 (b^3))

The zero sets are plotted in Figure . One sees from the curve intersections that there are two real solutions to the pair of equations, hence two real cylinders through this particular set of five points.

PROPOSITION 1. Configurations that give rise to an empty solution set or to a solution set of positive dimension lie on a variety in the configuration space.

PROOF (sketch). One obtains, in principle, a description of the generic solutions by forming a lexicographic Gröbner basis for the system (). The process of doing this gives rise to the generic basis because at steps along the way one is allowed to divide by polynomials in the indeterminates. All inputs that fail to give the generic basis thus must satisfy conditions among the coordinates that cause these polynomials, upon specialization, to vanish. As there are finitely many steps in forming the basis, there are finitely many such conditions. As these vanishing conditions are defined by polynomials, their union is a variety. We may further refine it. Some configurations might fail to give the generic basis but still yield a nonzero finite solution set. If we exclude the conditions that give this situation, we are still left with a variety for which we get either zero or infinitely many (complex valued) solutions. □

DEFINITION 1. Above we saw that the subset of nongeneric configurations that give either zero or infinitely many solutions comprises a variety. We refer to this as the "bad variety", denoted (Subscript[V, bad]). Several results below are stated in terms of configurations that miss this variety.

We remark that (Subscript[V, bad]) is a part of the discriminant variety (see []).

PROPOSITION 2. There is a nonempty open set in our configuration space (which is, in effect, (ℝ^15)) for which we obtain no cylinders in (ℝ^3).

PROOF. If one point is contained strictly within the convex hull of the other four then, as cylinders are convex, we have no real cylinders containing the five points. Small perturbations in real configuration space do not alter the situation that one is inside the hull of the other four. Hence there is an open set in real configuration space for which we obtain no real cylinders. □

COROLLARY 1. The maximum number of cylinders, already shown to be bounded by nine, is in fact no larger than eight.

PROOF. This is a consequence of the following facts. (i) Restricting to real inputs does not move us out of the generic case because this restriction is not algebraic. (ii) Given real data, complex solutions appear in pairs. (iii) The case where one point lies in the hull of the other four contains an open subset in the real part of the parameter space. Hence there is an open set in parameter space for which there are only complex solutions. So in general there must be an even number of solutions. □

This also shows that the the number cannot be seven. So we know it is either six or eight.

THEOREM 1. Five generic points in (ℝ^3) determine six distinct sets of cylinder parameters, of which an even number are real valued.

Proofs may be found in [] [] [] []. They make use of various algebraic or geometric features particular to this problem. An algorithmic approach in [] proves this blindly, that is, without use of geometry-specific features. (As with many algorithms in geometry, one can argue as to whether this is a good or bad thing, insofar as automated proofs often convey little insight. Regardless, algorithmic technology should not be ignored.) Proofs in [] count roots based on either a Gröbner basis or resultant computation from (). We give an independent proof below.

PROOF. We will count the solutions at infinity for the polynomials shown in (). We do this by homogenizing and setting the homogenizing variable to zero to get the initials (that is, the degree forms). They are

(-(b^3) (Subscript[x, 2]) (Subscript[z, 3])+(b^3) (Subscript[x, 2]^2) (Subscript[z, 3])+a (b^2) (Subscript[y, 2]) (Subscript[z, 3])-2 a (b^2) (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[z, 3])+(a^2) b (Subscript[y, 2]^2) (Subscript[z, 3]),-(b^3) (Subscript[x, 2]) (Subscript[z, 4])+(b^3) (Subscript[x, 2]^2) (Subscript[z, 4])+a (b^2) (Subscript[y, 2]) (Subscript[z, 4])-2 a (b^2) (Subscript[x, 2]) (Subscript[y, 2]) (Subscript[z, 4])+(a^2) b (Subscript[y, 2]^2) (Subscript[z, 4]))

The solution set for (a,b) consists of the three cases a->-b (1-(Subscript[x, 2]))/(Subscript[y, 2]), a->b (Subscript[x, 2])/(Subscript[y, 2]), and b->0. We thus obtain three solutions at infinity for the homogenized system (these are simply the directions of the three lines between any pair of the first three points). The number of solutions from the Bezout theorem, nine, counts these three, and hence there are six solutions in affine space. □

In [] a mixed volume computation is done in order to bound the number of solutions using a method presented in []. The value obtained in this computation is 8, and from [] we moreover know that that will be the generic number of solutions for problems with the same Newton polytope for monomial exponent vectors. To understand why this cylinder problem is not generic for the mixed volume computation, note that the initials are identical up to a constant multiple; any random perturbation (say, add (b^3) to the first polynomial) will give only one solution at infinity, and therefore yield 8 finite solutions.

PROPOSITION 3. There is a closed set with nonempty interior in (ℝ^15)-(Subscript[V, bad]) for which we obtain six real cylinders provided we count solutions by multiplicity.

PROOF (sketch). We may count the number of real roots using the Rule of Signs [] on the univariate polynomial in any generic lexicographic Gröbner basis. This gives a closed condition for the boundary of the set of configurations that yield six sets of real valued cylinder parameters. To show it has nonempty interior it suffices to demonstrate one such configuration that has no multiple solutions. But this is the case for the two six-real-cylinder examples shown in [] (one of which is formed from two regular tetrahedra sharing a common face). □

Similar argument shows that the sets in (ℝ^15)-(Subscript[V, bad]) that give rise to two or four cylinders real cylinders also have nonempty interiors. From Proposition 2 we already knew this to be the case for configurations that give no real cylinders.

It may be useful to look at Theorem 1 in the context of what are known as comprehensive Gröbner bases [] [] []. This construction in effect allows one to circumvent the problem that Gröbner bases are not continuous in their input data; indeed it seems designed to address that defect. Such a basis contains encoded all Gröbner bases, for a given ideal with respect to a specified term order, under all specializations of the parameters. It does so in essence by doing multiple polynomial reductions on a given polynomial in the basis, to simultaneously allow for the possibility that any nonnumeric leading coefficient might or might not be zero. The upshot is that the coefficients of the comprehensive Gröbner basis vary continuously in the parameters of the configuration. The typical use of such a basis is in concrete examples when one wishes to make case distinctions based on parameter values. When a lexicographic term ordering is utilized we can say a bit about the structure of such bases in the (generic) case of finite solution sets, using insight gained from our examples.

For instance, suppose we have six distinct solutions in a situation where the Shape Lemma [] does not apply (see [] for two such examples involving six distinct real valued cylinders). We consider the basis for such a numeric specialization of the general problem. From Gröbner basis theory we know it contains a univariate polynomial in the lexicographically last variable (say, a). The degree of this polynomial must be less than six as we have assumed the Shape Lemma does not hold for this particular ideal and term ordering. We refer to the remaining variables as "higher".

We return for the moment to the general case wherein coefficients are again indeterminate parameters that vary in our configuration space. Note that a comprehensive Gröbner basis encodes, in vanishing conditions of leading coefficients, the basis for specializations of the sort just described. It also encodes the generic basis. By the Shape Lemma this latter contains linear polynomials in each of the higher variables with lead coefficients that generically do not vanish. By [] all parametrized coefficients of at least one such linear polynomial must become identically zero for the nongeneric type of specialization under consideration (otherwise we would have fewer than six solutions). Hence the comprehensive basis must also contain nonlinear polynomials in those variables.

Now consider a generic specialization of the configuration parameters. Again invoking results from [] we know that solutions are obtained from the subset of the comprehensive basis that encodes the generic case (that is, the generic degree six univariate polynomial and the polynomials that are linear in each of the higher variables). These are shown also to satisfy those polynomials that are nonlinear in the higher variables. So such a linear polynomial (say, in the variable b) must have the form f(params) (b-g(a)) where the second factor divides any corresponding polynomial(s) of higher degree in b. In other words, when the first factor, which involves only parameters, is nonzero, then where the second is satisfied all those in higher degree must also be satisfied; moreover they cannot all vanish when the first factor vanishes, so they must be divisible by the second factor.

. Configurations With no Real Solutions

THEOREM 2. Suppose we have four noncoplanar points in (ℝ^3). They are the vertices of some tetrahedron. Then there is an open set S containing the open tetrahedron and a dense subset of its boundary in the configuration space, such that if the fifth is chosen in S there will be no real cylinders containing all five points.

REMARK. If the fifth point is inside the convex hull of the other four then we already know this result. Now take the tetrahedron formed by the four points. Through each vertex the planes containing the three coincident faces form a cone with triangular base. If the fifth point lies within that cone then it obscures that vertex, i.e. the vertex lies inside the new tetrahedron formed by the fifth point and the remaining three. Hence this case is also covered by the "one point in the hull of the others" situation. Note that in this case the fifth point need not be near in distance to the other four.

PROOF 1. Suppose the fifth point lies on a face of the tetrahedron formed by the other four. Then the convexity argument still tells us that no cylinder in (ℝ^3) can contain all five points. As we assumed the tetrahedron coordinates are generic, we are in one of two situations: either having the fifth point lie on a face formed by three others puts the configuration in (Subscript[V, bad]) or it does not. We show that generically it does not, or in other words, the algebraic condition that four points are coplanar is not a condition for the bad variety. That this is so follows from the trivial observation (verified computationally) that there are configurations with four coplanar points that give rise to lexicographic Gröbner basis with the generic "shape"; were this a condition to lie in the bad variety then every configuration with four coplanar points would be in it.

The preceding argument shows that generically the fifth point is not on a tetrahedral face of the other four, so the set of such fifth points is dense in the set of all boundary points of the tetrahedron. By genericity we may assume that we have a univariate polynomial of degree six for one of the cylinder parameters. As there are no real cylinders containing this configuration, this polynomial has exclusively nonreal roots. These roots vary continuously with the configuration, hence the imaginary parts remain nonzero under small perturbations of the five points. Thus there is an open set around this point on the boundary for which we still obtain no real roots. As we require real roots in order to obtain cylinders in (ℝ^3) this suffices to finish the proof. □

PROOF 2. This line of reasoning was suggested by [Richard Bishop, private communication]. In order for all five points to lie on a cylinder there must be a plane tangent to the unit sphere, and a circle in that plane, such that they all project onto that circle. Suppose the fifth point is inside or on the boundary of the tetrahedron formed by the other four. Then it is clear that the projection of the five points onto any such plane will have the projection of this last point contained in the quadrilateral formed by the projection of the other four. Hence any quadratic in the plane that contains all five projected points must be a hyperbola (because all other quadratic curves are convex). Moreover the parameters of the hyperbola equation are continuous in the locations of the five points. As the set of projection planes is compact, a small perturbation of the fifth point beyond the hull of the other four will not alter the situation that the five points project onto hyperbolas in all such planes, hence they cannot lie on any cylinder in (ℝ^3). Hence from every boundary point on the tetrahedral hull of the four points, we may perturb outward some minimal distance (depending on that boundary point) and still have no real cylinders. As the tetrahedron boundary is compact we deduce that there is a minimum positive distance we can move outside and still not get real cylinders. □

COROLLARY TO PROOF. There is an open set S containing the closed tetrahedron, such that if the fifth is chosen in S there will be no cylinders in (ℝ^3) containing all five points. In other words, the "bad" variety in configuration space is not an issue.

We now wish to show that all configurations that give no real cylinders arise in the setting of Theorem 2. Specifically we state the following conjecture.

CONJECTURE 1. Suppose we have a configuration of five points in (ℝ^3) for which no real cylinders exist, and moreover assume that no point lies in the hull of the others. Then one of the points can be moved anywhere inside the convex hull of the full set and still we will get no real cylinders. In particular we could move this point along a line segment from outside to inside the hull of the other four, and at no point on that path would we get real cylinders. Thus we could regard the given configuration as a perturbation of one that has one point inside the hull of the other four, effectively providing a converse to Theorem 2.

We make observations of sufficient conditions for a proof and then state as a theorem a special case wherein we can fullfill the conditions. First consider the two curves that are solution sets to the two polynomials in (). They are cubics that have one or more closed topological components in two dimensional real projective space, and because they are cubic they each have at least one real component that goes to infinity. (It is well known that they are connected as complex curves; by "components" we mean the obvious thing with respect to intersections with real space.)

We regard each point on such a curve as a solution to the direction parameter equations given by the four points in configuration space lying on a cylinder with axis in that direction. In other words, each point on the solution curve in parameter space defines a cylinder through the four points in configuration space that were used to form that equation. Suppose that at a solution on one such component, the fifth point lies inside the cylinder thus obtained (we are being loose with terminology but trust the meaning of "inside a cylinder" is clear).

Claim: For generic configurations it must then lie inside all cylinders defined by points on that affine component of the solution curve.

The proof of this claim has a small complication. Specifically, we must show that in order for the fifth point to "escape" outside the cylinder containing the other four, it must cross that cylinder (in contradiction to our hypothesis that there are no real cylinders containing all five points). A priori there is another way it might escape: the cylinder containing four can degenerate to a plane and subsequently reverse its "open" side. This degeneration can arise if the four points project onto a line for some direction. Such a direction must then lie in all four planes containing three of the four points. This gives an overdetermined and generically inconsistent set of linear conditions. We thus have verified the claim for generic configurations: if the fifth point is inside a cylinder containing the other four, then it stays inside the cylinders defined by all points on that component of the solution curve, and these cylinders each contain the other four points.

Next we observe that, were this true not just on one topological component of the direction solution curve, but on all of them, then that fifth point works in the conjecture. We see this as follows. When the fifth point lies inside all cylinders defined by a solution curve component, then it projects along the cylinder axis to a point inside the circle that intersects the projections of the other four. The same must hold for any other point in the interior of the convex hull of the five points. This is because such a point, written as a convex combination of the five, must either be in the interior of the tetrahedron defined by the first four (and thus project to the interior of the circle they define), or else have a nontrivial component of that fifth point and again thereby project to that circle interior.

We now proceed to construct a solution on one direction curve, that is, a cylinder containing four of the points, such that the fifth is inside it. We can arrange our four so that three are in the x y coordinate plane and the remaining two have a segment joining them that intersects the triangle defined by the first three (using a rotation, such an arrangement can always be found for a configuration of five points in (ℝ^3)). We place the fourth point on the z axis beneath the origin. Projecting from the fourth point onto a plane in the direction of the segment between the fourth and fifth points gives a unique circle containing the first three. The cylinder along that direction and containing that circle thus encloses the fourth and fifth points. Now we simply move one of the direction coordinates, forming new projections and cylinders containing the first three points, until one of the remaining points (say, the fourth) hits that cylinder. What we have done is to arrive on one of the two direction solution curves we set up in (). Thus we obtain a cylinder containing four points and enclosing the fifth. From the discussion above we know that this holds for all cylinders defined by this affine component of the curve of directions.

At this point we have a sufficient condition for the conjecture to hold. We simply require that each of the solution curves have only one affine component.

THEOREM 3. Given five points in (ℝ^3) for which there are no real solutions to the cylinder equations, suppose there are three such that
(i) The segment joining the remaining two intersects the triangle bounded by those three.
(ii) The two curves of solution directions for cylinders containing those three and either the fourth or fifth respectively, each have only one component in real projective space.
Then either the fourth or fifth point can be moved anywhere inside the hull of the five and there will be no real cylinder containing this new point and the other four.

As remarked above we can always order the points in such a way that the first condition holds. But then in general the second condition will not hold. We believe the conjecture to be true all the same, though we do not have a proof at this time. We also mention that extensive graphical evidence suggests that most often these curves have one component in two dimensional real projective space. This is found by taking random examples with three points in the x y coordinate plane and the fourth and fifth above and below respectively, throwing away those that have real solutions, throwing away from the rest those for which the segment between fourth and fifth points does not go through the triangle bounded by the first three, and plotting the zero level sets for the two cylinder equations in remaining cases.  "Most often", in this setting, refers to specifics of how we select our five points; we use pseudorandom values in a unit interval for each of the free parameters. In any case it would seem that this method applies frequently to configurations that give rise to no real cylinders. Finally, we remark that such curves have either one infinite component, three infinite components, or one infinite and one finite component (homotopic to a circle). This is easily shown by a root counting argument.

We illustrate with a configuration that meets the conditions of the hypotheses. There are no real cylinders containing the set of points (0,0,0), (2,0,0), (1,2,0), (5/4,1,1/2), and (3/4,1,-1/3). This point set is shown in Figure . It may be seen that the segment joining highest and lowest points pierces the triangle formed by the other three.

Here are the direction parameter polynomials obtained by requiring that the fourth and fifth points respectively project onto the circles determined by the first three points and a given direction vector.

(-575-40 a-384 (a^2)-40 b-200 a b+160 (a^2) b-159 (b^2)-40 (b^3),-207-24 a-128 (a^2)+24 b+72 a b-96 (a^2) b-47 (b^2)+24 (b^3))

Figure  plots of their respective zero sets. It is clear from the way the respective affine parts will meet at infinity that each has one topological component in real space, and moreover they do not intersect at finite points. Hence Theorem 3 applies to this configuration.

Note that we can weaken the second hypothesis of Theorem 3 so that the curves may have multiple components, provided the components for one are not separated by any component of the other. Graphical evidence supports the belief that this weaker requirement is always satisfied. Clearly a proof to this effect would suffice to prove the conjecture.

. Configurations that have six real solutions

We describe in brief two cases that have six solutions. Further detail may be found in [].

(1). Start with four points forming vertices of a square in the x y plane. This is the base of a pyramid with the fifth point as its apex above the centroid of this square. We obtain two horizontal cylinders each passing through a pair of opposite triangular faces of the pyramid. The remaining four each pass through a triangular face, angled upward, and an edge of the base. This case was first posted in [].

(2). Take as five points the vertices of  two regular tetrahedron sharing a common face. This presents an interesting set of symmeries. Any cylinder will have a "mirror image" obtained by reflection across the joined face, and also have two "conjugates" obtained by rotation of π/3. We show a visualization of this in Figure ; the common face lies in the horizontal plane.

We now show the planar curves in real space that one obtains from the pair of cocircularity conditions in (). We also perturb the five points slightly and show the resulting intersections. This is because the unperturbed case is a degenerate setup and the actual curves are each three lines. The perturbation indicates how each triad of lines can split at intersections into pairs of curves in the projective plane.

This configuration has some interesting properties. If the tetrahedron edge length is (Sqrt[3]) then the common cylinder radius is 9/10. It is related to a configuration from [], wherein we have four points and a fixed radius for which there are twelve real cylinders through the points. For that we take vertices of one of the tetrahedra as our four points, and 9/10 as the common radius. We obtain four sets of six cylinders by gluing tetrahedra respectively to each face of the given one. But these pair off for a total of twelve cylinders.

This configuration is also, perhaps surprisingly, related to the case of no real cylinders. We start with the doubled regular tetrahedra. There are two vertices not on the common face. Now let one of them move along the axis connecting it to the other. The two and three fold symmetry considerations indicated above imply that we either have six real cylinders (counting multiplicity), or none. It is not hard to realize that either moving it "too close" or "too far" from the opposite vertex gives rise to a configuration approaching the case of one point inside the hull of the other four. This is quantified in an explicit computation in []. It is also makes for an interesting dynamic geometry visualization to change the one vertex and depict the six cylinders coalescing into three pairs (multiple roots) before vanishing from real space [].

It is an interesting question whether all cases of six real cylinders arise as "perturbations" of the two cases discussed above. As a starting point it would be useful to know whether they can be perturbed into one another with six real cylinders for every configuration along the perturbation.

. Nongeneric Configurations

Thus far we have discussed exclusively the generic situation. It is of interest to make a few observations about the nongeneric case. This in turn sheds light on cylinder solutions for point configurations that are generic but "near" to such nongeneric ones.

PROPOSITION 4. Sets of five coplanar points are not generic insofar as they do not give six solutions to the cylinder equations. In general they give four such solutions.

PROOF. This follows from a straightforward computation with the pair of polynomials from (). We substitute zero for the two nontrivial z parameters and compute a Gröbner basis in terms of the cylinder direction variables (a,b). This is in the form specified by the Shape Lemma and has a univariate polynomial of degree four with a second polynomial linear in the remaining variable. Hence for coplanar configurations there are generically four solutions rather than six. Of course there are further degeneracies that can arise. If, for example, four of the points are collinear then there will be infinitely many cylinders containing all five.

To finish the proof we must show that there are no cylinders parallel to the x y coordinate plane (as we tacitly set the z coordinate of the normal vector to 1). But this is clear from the fact that such a cylinder would intersect the coordinate plane in a pair of lines, and generically the five coplanar points do not lie on any pair of lines. □

COROLLARY. As configurations of five points move toward a generic coplanar configuration, two of the six (possibly complex) cylinder solutions go to infinity.

This shows that in any comprehensive Gröbner basis for the system, using a lexicographic ordering, the univariate polynomial of generic degree six has leading and second coefficients vanish when the points are coplanar. The third coefficient will in general not vanish in this situation.

We now describe what happens in the generic coplanar case.

THEOREM 4. Given five coplanar but otherwise generic points in (ℝ^3) there are four (complex) cylinders containing them. Of those, either zero or two will be real cylinders.

PROOF. That there are four complex cylinders was noted in the proof to Proposition 4. The five points uniquely determine a quadratic curve in the plane in which they lie, and generically it is either a hyperbola or an ellipse. The intersection of a cylinder with a plane is likewise a quadratic in that plane. Thus any cylinder containing five coplanar points contains the entire quadratic curve they determine. If that curve is a hyperbola then no real cylinder can contain it. If instead it is an ellipse then there are two real cylinders that contain it. These two cylinders have radial axes that each go through the center of the ellipse and lie in the plane perpendicular to the ellipse minor axis, and their angle of intersection is determined by the eccentricity of the ellipse. □

For illustration we show in Figure  the case of two real cylinders when the points (all in the x y coordinate plane) are (1, 0, 0), (-1/3, 1, 0), (4, -1, 0), (1/2, 2/3, 0), and (1/4, -1, 0).

We can use the computational construction () to shed light on the problem of counting the number of cylinders of a given fixed radius through four points (which, as noted in [], is equivalent to the problem of counting the number of lines simultaneously tangent to four given spheres of equal radius). As the radius is fixed (say, to 1), we are no longer free to rescale so we would use ((Subscript[x, 1]),0,0) for our second point. We would project to circles using only two points along with the given radius. An important difference to arise is that for projections of two points onto any given plane, there are two circles of the given radius containing them. This ansatz would lead us to expect twice as many solutions for this problem as we obtained for counting cylinders through five points. That there are in fact twelve (not necessarily real valued) cylinders of given radius through four generically placed points is a theorem in []. In the special case that the points are coplanar, that there are eight such cylinders is a result of []. All of them can be real valued which is an interesting contrast to the result of Theorem 4 above. We remark that the generic number of complex solutions to these systems is obtained algorithmically in [].

We would like a converse to Proposition 4. We begin with the observation that any configuration with four (or five) collinear points, or three collinear points and the remaining two on a parallel line, will contain infinitely many cylinders. We would like to know whether these are the only configurations for which that is the case. We note that a similar situation was shown in [] for having infinitely many lines tangent to four given spheres.

Once three noncollinear points are fixed in a plane, there are finitely many ways to combine the remaining two points such that one of the above conditions holds. For any such combination, there are two degrees of freedom in how the points are placed. We will show that this is consistent with dimensional considerations.

Suppose we have infinitely many solutions. If they arise from but finitely many axial directions, then one can readily show that any infinite solution set comes about from four collinear points or points lying on two parallel lines, so that the axis is uniquely determined. We now assume this is not the case, that is, we have infinitely many axial directions. Consider our axial direction cubics from (). In order to have infinitely many solutions, the algebraic curves that are solution sets to these two polynomials must share a component. That is, on a component of directions in which four points project onto a circle, the fifth must project onto that same circle.

Observe that cubic equations of the form imposed by our choices above have eight degrees of freedom (general cubics have ten coefficients but ours lose one degree three term, and the cubics are only defined up to nonzero scalar multiplication, giving eight degrees of freedom). Hence pairs of cubics of that form have sixteen parameters. The set of pairs we can actually attain has eight degrees of freedom (from the eight coordinates not a priori known). In order that a pair share a component, they must factor (they cannot be identical unless a pair of points coincides, in contradiction of hypotheses). The set of pairs that share a common factor has dimension ten. Thus we expect the dimension of the set of attainable cubic pairs that share a component to be given by the intersection dimension, which is two.

CONJECTURE 2. Any configuration of five distinct points for which there is a dimensional component to the cylinder parameter solution set must be coplanar. Either four points are collinear, or three are collinear with the remaining pair on a line parallel to that containing the first three.

This conjecture, alas, is not true as stated. In particular it does not hold in complex space. Here is a specific configuration violating the hypotheses, for which the solution set is infinite.

(0,0,0),(1,0,0),(-2,8/5-(6 i)/5,0),(2,-2,1),(-2,14/5+(12 i)/5,-3)

It remains an open question whether there are configurations with real coordinates which comprise a counterexample to the conjecture. Attempts to prove this via computational tactics (formulate relations based on factoring of the polynomials and equating a pair, finding relations among the data parameters, then checking that no real solutions can exist) have foundered to date due to computational complexity. That complex solutions can exist is already a bad sign insofar as it means one must use real solving technology e.g. cylindrical algebraic decomposition, and this is known to be computationally intensive.

. Summary

We reviewed in brief the fact that there are generically six solutions to the equations for cylinders through five points in (ℝ^3), noting that of these any even number, counting multiplicity, may be real valued. We discussed in some detail the case where there are no real valued solutions. Specifically we have a theorem and conjectured converse relating the case of no real cylinder solutions to perturbations of having one point within the convex hull of the other four. We also described configurations for which there are six real solutions.

We proceeded to the special case where the points are coplanar. In this situation generically there are only four solutions, and, in contrast to the noncoplanar case, at least two are not real valued. When two are real valued and distinct, small perturbations from coplanarity will not alter this situation. A natural question is whether there is a plausible conjecture, similar to that for the case of no real cylinders, to the effect that all cases of two real cylinders are perturbations of coplanar cases.

It would be interesting to get a geometrical description of what configurations will give rise to the other numbers of real valued cylinders. In [] it is observed that all computational examples observed having six real solutions appear to be perturbations of the two particular configurations we mentioned. But this is quite far from a systematic understanding of the geometry of five point configurations that give six real solutions. We seem to know even less about the case of four real solutions.

Related to the geometric classification of where the number of real or complex solutions changes, there is the algebraic description via real and complex algebraic sets. From this point of view it would be nice to better understand the discriminant variety [], []. Unfortunately this seems to be computationally intractable using existing technology.

. References

E. Becker, M. G. Marinari, T. Mora, and C. Traverso. The shape of the Shape Lemma. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 94). 129-133. ACM Press, 1994.

T. Becker, W. Weispfenning, and H. Kredel. Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics 141. Springer-Verlag, 1993.

C. Borcea, X. Goaoc, S. Lazard, and S. Petitjean. Common tangents to spheres in (ℝ^3). Discrete and Computational Geometry 35(2):287-300, 2006. Also available as technical report: INRIA Rapport de recherche 5325.

O. Bottema and G. Veldkamp. On the lines in space with equal distances to n given points. Geometriae Dedicata 6:121-129. D. Reidel Publishing Company, 1977.

J. Bryant and D. Lichtblau. Wolfram Demonstrations Project CylindersThroughFivePoints, 2007.
http://demonstrations.wolfram.com/CylindersThroughFivePoints/

T. Chaperon and F. Goulette. A note on the construction of right circular cylinders through five 3D points. Technical Report, Centre de Robotique, Ecole des Mines de Paris. 2003.

T. Chaperon, F. Goulette, and C. Laurgeau. Extracting cylinders in full 3D data using a random sampling method and the Gaussian image. In Proceedings of the of the 6th International Fall Workshop Vision, Modeling, and Visualization (VMV '01), Stuttgart, Germany, November 2001. T. Ertl, B. Girod, G. Greiner, H. Niemann, and H-P. Seidel, eds. 35-42, 2001.

O. Devillers, B. Mourrain, F. Preparata, and P. Trebuchet. On circular cylinders by four or five points in space. Discrete and Computational Geometry 28:83-104, 2003.

C. Durand. Symbolic and Numerical Techniques for Constraint Solving. Ph.D thesis. Purdue University, Department of Computer Science, 1998.

C. Hoffmann and B. Yuan. On spatial constraint solving approaches. In Proceedings of the Third International Workshop on Automated Deduction in Geometry (ADG 2000). J. Richter-Gebert and D. Wang, eds. Lecture Notes in Computer Science 2061:1-15.  Springer-Verlag, 2001.
See also: There are 12 common tangents to four spheres, 2000. Website URL: 
http://www.cs.purdue.edu/homes/cmh/distribution/SphereTangents.htm

M. Kalkbrenner. Solving systems of algebraic equations by using Gröbner bases. In Proceedings of the European Conference on Computer Algebra (Eurocal 87). J. Davenport, ed. Lecture Notes in Computer Science 378:282-292. Springer-Verlag, 1989.

D. Lazard and F. Rouillier. Solving parametric polynomial systems. Journal of Symbolic Computation 42(6):636-667, 2007.

D. Lichtblau.  Cylinders through five points: computational algebra and geometry. Manuscript, presented at the Second International Congress on Mathematical Software (ICMS 2006). Session "Software for Algebraic Geometry and Related Topics", Nobuki Takayama organizer. Slides and video available courtesy of Professor Takayama, Kobe University, Japan:
http://www.math.kobe-u.ac.jp/icms2006/icms2006-video/video/v001.html

D. Lichtblau.  Simulating perturbation to enumerate parametrized systems. Manuscript.

I. G. Macdonald, J. Pach, and T. Theobald. Common tangents to four unit balls in (ℝ^3). Discrete and Computational Geometry 26(1):1-17, 2001.

M. Manubens and A. Montes. Improving the DISPGB algorithm using the discriminant ideal. Journal of Symbolic Computation 41(11):1245-1263, 2006.

M. Manubens and A. Montes. Minimal canonical comprehensive Groebner systems. ArXiv preprint:
arXiv:math/0611948v2 [math.AG], 2007.

G. Megyesi. Lines tangent to four unit spheres with coplanar centres. Discrete and Computational Geometry 26(4):493-497, 2001.

B. Mishra. Algorithmic Algebra. Springer-Verlag, 1993.

A. Montes and T. Recio. Automatic discovery of geometry theorems using minimal canonical comprehensive Groebner systems. ArXiv preprint:
arXiv:math/0703483v1 [math.AG], 2007.

D. Rusin. Website URL:
http://www.math-atlas.org/98/5 pt.cyl

E. Schömer, J. Sellen, M. Teichmann, and C. Yap. Smallest enclosing cylinders. Algorithmica 27:170-186, 2000.

B. Sturmfels. Polynomial equations and convex polytopes. American Mathematical Monthly 105(10):907-922, 1998.

V. Weispfenning. Comprehensive Gröbner bases. Journal of Symbolic Computation 14(1):1-29, 1992.