High Performance Symbolic Computing and Challenges of Computer Algebra

**Solving the Six-Line Problem with the Dixon Resultant***

The "Six-Line Problem" arises in the automated analysis of images. A
three-dimensional object is photographed and from the photographs (or other
means) a set of geometric invariants are obtained by techniques of algebraic
geometry. These *three-dimensional invariants* represent six lines
abstracted from the object. Suppose that later an object is encountered and
a photograph taken. The problem is to decide if this is the same object as
before. From the flat photograph, *two-dimensional invariants* may be
obtained.

The relationship between the three- and two-dimensional invariants may
be expressed as a set of polynomial equations. The photographed object is
the right one if the set of equations has a solution. One well known method
to solve such sets of equations is with *resultants*. The number of
variables and the size of the matrix seemed overwhelming until recently.

At IMACS '97 Lewis described how a solution was obtained using the Dixon-Kapur-Saxena-Yang resultant, given the 3D invariants of a particular object. In this talk we describe how the entire resultant may be obtained once and for all using the same resultant method. The technique may well be applicable to any problem that needs to compute a multivariable resultant.

Robert H. Lewis

Department of Mathematics

Fordham University

rlewis@murray.fordham.edu

George Nakos

Department of Mathematics

U. S. Naval Academy

gcn@nadn.navy.mil

*****Research supported by the Office of Naval Research.

IMACS ACA'98 Electronic Proceedings