Cylinders Through Five Points: Complex and Real Enumerative Geometry

Daniel Lichtblau
danl@wolfram.com

Wolfram Research, Inc.
100 Trade Centre Dr.
Champaign IL USA, 61820

ADG, Pontevedra, Spain
August 31-September 2, 2006

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.

Introduction

The problem

Given five generic points in (ℝ^3) we wish to know how many cylinders pass through them. By setting up a system of polynomial equations this can be construed as a problem in complex space though of course the focus of most interest is on the real solutions. We will consider aspects of both. When I say "cylinders" I mean to include both complex and real solutions to the equations that describe right circular cylinders through a set of five points.

Why is this of interest?

There are constraint geometry applications:

Find smallest cylinder enclosing five given balls of equal radius.

Find cylinder best fitting many points (one might first find an exact fit to five points, then use optimization to get a least squares best fit to all points). Useful in scene reconstruction, tolerancing, helical molecular structure recognition...

Related to other constraint geometry problems e.g. find cylinders of given radius through four given points (applications to scene occlusion and elsewhere).

Can be tackled computationally in several ways. Or one can use pure theory if so inclined...So problem is ripe for exploration.

The enumerative geometry itself is interesting. The possible numbers of real cylinders for coplanar configurations is strictly less than the number of complex solutions.

Introduction

Contribution of this work

Several ways to show there are, generically, six solutions.

Better understanding of situation in which there are no real solutions.

Better understanding of nongeneric cases.

This is a work in two parts. The next, which I think of as "part 1", is to be presented in a few days at ICMS. It will focus more on the computational tactics I have used over the years to work on this. Of course there is some overlap in the actual talks.

Why you should not work on this

It is mildly addictive.

Setting up the problem

We algebraicize to get two equations in two unknowns. We use a "generic" formulation of the axial direction vector.

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 two polynomials in {a,b} 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)}

Setting up ...

Immediate observation: Each is cubic in {a,b} so the Bezout formula shows there are at most nine solutions.

Less immediate: The number of solutions is even, so there are at most 8. Follows from:
(1) Real data coordinates force complex solutions to appear in pairs
(2) There are "open" sets of configurations with no real solutions.

Remark: A mixed volume computation also gives 8. So this family of problems is degenerate from the point of view of mixed volume solution counts.

The actual solution count

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

First proved by Bottema and Veldkamp (1977).

Other proofs have been devised in recent years:
Chaperon and F. Goulette (2003)
Devillers, Mourrain, Preparata, and Trebuchet (2003)

Proving the actual solution count

I have a few proofs that are, to varying extents, computational.

Proof 1 (used in this paper): Count the solutions at infinity by homogenizing and getting the degree forms. Find that there are three, hence there are six affine solutions.

Proof 2: (i)Take a random set of values for the parameters. Solve the axis direction equations. Obtain six solutions. This shows the generic count is at least 6 (and "shape lemma" implies it is almost certainly exactly 6, or you have a bad random generator).
(ii) Now form the resultant with respect to b, obtain a polynomial of degree 6 in a. This shows it is at most 6.
(iii) Tricky step (uses deep result from real analysis...) Observe 6≤|solns|≤6 implies |solns|=6.

Proof 3: Compute a Gröbner basis for the polynomials in {a,b} with respect to a convenient term order. The coordinates involve parameters that are "coefficients" for purposes of this computation. Count the size of the "normal set" (monomials not divisible by the basis lead monomials). This gives the number of solutions, and it is six.

Proof 4: Show there are six solutions not just to a particular configuration but to all configurations in some neighborhood thereof. This is work in progress; it uses symbolic perturbation approach that might also be applicable to actual perturbation problems e.g. approximate gcd.

Counting real solutions: Basics

What can we say about how many real solutions there might be?

Obvious: When we restrict point coordinates to real values, since complex solutions pair off there are an even number of real solutions counted by multiplicity.

Easy to show: In this setting, any of the possible numbers (0, 2, 4, or 6) may arise, and indeed there are open sets in real parameter space that give rise to each possible real cylinder count.

(1) Beyond this, fairly little is known about classifying the cases of various possible numbers of real solutions.
(2) I will indicate what I do know, and say a bit about why I think this classification problem is hard.

Case 1 of six real solutions

I am aware of two configurations that readily give six cylinders. The first uses points on a pyramid with square base and equilateral trinagular faces. We get four cylinders like the first one below (cutting base and one face), and two like the second (through pairs of opposite faces).

Case 2 of six real solutions

The second uses points on two regular tetrahedra that are glued along a common face. This gives rise to six solutions, two of which are shown below.

I find this configuration to be interesting because a simple perturbation, moving the top point  upwards vertically, will reach a point at which we go from six to zero real solutions. Also of interest: it is closely related to a case where the common tangent to four given spheres has all solutions real (12 of them).

I have a vague belief, which I elevate to "conjecture", that any configuration with six solutions is in some sense a perturbation of one of the two described above. Of course this does not rule out that they may be perturbations of one another. (What does this mean? That one can move points to go from one to the other in such a way that there are six solutions at every intermediate configuration.)

Case 2...

Cases of no real solutions

One-inside-four situation, and nearby configurations

Basic observation: If one point is in the convex hull of the other four then there are no real cylinders containing all five.

Reason: All projections along any direction onto a plane orthogonal to that direction will keep that one point in the hull of the others. So the projected five points cannot be cocircular. But if they lie on a cylinder there is a projection (in real space) where they become cocircular, to wit, projection onto a plane perpendicular to the cylinder axis.

Theorem: We can have that point inside move "slightly" outside the hull of the other four and still have no real cylinders containing all five.

Proof sketch: When the fifth point is in the hull of the others all projections have the five lying on hyperbolas (five points in a plane determine a quadratic). As we move the point to the hull boundary and slightly outside along any path, these projected quadratics remain hyperbolas, hence there is no direction of cocircularity.

Geometric understanding of no real solutions cases

More generally...

Conjecture (partly proven): If we have a configuration that yields no real cylinders then it is a perturbation of a configuration of one point in the hull of the rest (again, this means we can move a point inside the hull in such a way that all intermediate configurations have no real cylinders).

We make some observations:

The vanishing set of the first direction equation polynomial in the a b plane (a curve) corresponds to directions (a,b,1)  where the fourth point is cocircular with the first three. Likewise the second vanishing set is for directions where the fifth is cocircular with the first three.

So...the directions for cylinders containing all five are the intersections of these two curves.

Take a configuration with no real cylinders. Say the first curve has one topological component in the real plane (this appears to be a common situation). Also suppose that in some direction given by a point on this curve, the remaining configuration point (the fifth one) projects inside the cylinder containing the first four. Then it stays inside all cylinders determined by the first four points. (Reason: if it moves outside, then in some direction it actually hits and we have a cylinder containing all five points).

No real solutions...

Next note that this holds for ANY point in the interior of the hull of the five given points. Reason: If a point is in the hull of the first four, it is inside any cylinder containing them. If not it is a convex combination of the five points with nontrivial component of the fifth, hence will project inside any circle containing projections of the first four (because we know the fifth projects inside).

Arrange first four points 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. We place the fourth point on the z axis beneath the origin.

No real solutions...

More observations:

Projecting from the fourth point onto a plane in the direction of the segment between the fourth and fifth points gives a unique a 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. 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 component (in the real plane) of the curve of directions.

Conclusion: We can formulate sufficient conditions for which a configuration with no real solutions can be perturbed so that one point is in the hull of the other four. A sufficient condition, for example, is that each of the cubic curves for the cocircularity directions of four points have one component in the real plane.

Example with no real solutions

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). Observe that the segment joining highest and lowest points pierces the triangle formed by the other three.

Example...

Here are the direction parameter polynomials for this example:

(-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))

We plot the vanishing curves.

As each has one component in real projective space (look at how they connect "at infinity") we see this conforms to the sufficient condition mentioned earlier. Hence we can move one of the points inside the hull of the others at everywhere on the path have no real solutions.

Nongeneric configurations, in brief

Five coplanar but otherwise generic points will give four (complex-valued) cylinders.

Of these, either zero or two will be real valued (second case illustrated below). This is an interesting contrast to the case of cylinders of given radius through four coplanar points. In that case there are eight solutions, and ALL can be real valued (Megyesi, 2001).

CONJECTURE: Any configuration of five distinct points for which there is a dimensional component to the cylinder parameter solution set must be coplanar. Moreover either four of the points will be collinear or three will be collinear with the line determined by the remaining two being parallel to it.

Nongeneric configurations, in brief

Why is this hard to show?

Computationally: The computations might be attempted by Gröbner basis methods. A problem is to enforce that all five points are distinct. This can be done by introducing new variables and polynomials but the complexity seems to become exorbitant.

Mathematically: I have not come up with a good formulation. But maybe someone with better ideas will succeed at this. Related: a recent article by Borcea, Goaoc, S. Lazard, and Petitjean discusses the infinite solution case of a tangent to four fixed spheres with coplanar centers, showing a result involving collinearity.

Summary

Given five points in real space...

What we know

There are six cylinders in complex space that contain them.

Any even number of which may be real cylinders.

We have a geometric idea of how to classify cases for which there are no real solutions (as perturbations of cases where one point is in the hull of the others).

We have two types of examples that give six solutions. Each has considerable symmetry. All other pseudorandom cases I have observed appeared, visually, to be a perturbation of one of these.

We have a family of examples that gives two solutions (coplanar points lying on an ellipse in that plane). Do perturbations of this describe all cases? (I doubt it.)

Summary

What we do not know

We have no proven classification of the cases that give solutions with dimensional components.

We have no algebraic description of the cases of no real solutions. Such a classification might be obtainable, say, by understanding the discriminant variety of the ideal of axial direction polynomials in the product space of directions x point coordinate parameters.

We have no (plausible) conjectures that describe the cases of two or four real solutions.

In application settings one expect to have real solutions. Is there a "typical" number in such settings? (Is it, say, two?) Might this knowldege be useful for practical reasons?