Implicitization

From ErgaWiki

Revision as of 16:08, 9 March 2012

Implicitization experiments on curves and surfaces

Implicitization is the change of representation of a (hyper)surface, from a parametric one to an implicit, or algebraic, representation. The former describes the geometric object as the set of values of parametric expressions over a set of values of the parameters. The latter describes the same object as the zero-set of a single polynomial. Example: the unit circle is given parametrically by x=cos(t), y=sin(t); its implicit equation is x^2+y^2=1. We shall call x,y the implicit variables.

For the case of curves, there are two parametric equations in one parameter. For the case of surfaces, there are 3 parametric expressions in two parameters. Each parametric expression can be transformed to a polynomial. For example, the expression x=f(t)/g(t), is transformed to the polynomial F(t)=x*g(t)-f(t). We consider the system of all such polynomials and define its sparse resultant. At this point, our first approach was to compute the Newton polytope of the sparse resultant, or resultant polytope, and then to recover from this polytope the Newton polytope of the implicit equation, or implicit polytope. This method was very inefficient as it can be seen in the examples below. We follow a more direct approach and compute a projection of the resultant's Newton polytope, without computing the resultant polytope itself. This projection gives information on the implicit equation's support and it is defined by the coefficients of the polynomials which involve implicit variables. Then, we compute the implicit equation by interpolation, which amounts to linear algebra.

The first section contains experimental results on the support prediction step which is the computation of the resultant polytope, or its projection, given the system of polynomials constructed by the parametric expressions. Let us describe our first apprloach. The supports of the polynomials, transformed by the Cayley trick are stored in the files in the "supports" column. The file format is as follows: the first line contain the number of points and their dimension and in the following lines each column contains the coordinates of a point. The method used here retrieves the resultant polytope from the computation of another polytope called secondary polytope. We use TOPCOM [1] to compute the vertices of the secondary polytope each of which gives us a vertex of the resultant polytope. The secondary polytope's vertices are more numerous than the resultant polytope's vertices, as shown in the experiments below. To overcome the inefficiency of computing secondary polytopes, we developed an output-sensitive algorithm for computing resultant polytopes and their projections [2]. Its implementation, called ResPol can be found in [3].

Let us demonstrate how to prepare the input for ResPol, given the parametric equations of a surface: $x=1/2s^2-1/2t^2-1/4s^4+3/2s^2t^2-1/4t^4, y=-st-s^3t+st^3, z=2/3s^3-2st^2$.

Implicitization using predicted support has been implemented in Maple. In our experiments we use two support prediction methods: one applies only for curves and can be fully implemented in Maple, another is general (implemented in respol). We present our Maple implementation of the implicitization with predicted support and some examples. Here we apply numeric (SVD) as well as exact methods for linear solving in order to obtain coefficients of the implicit equation.

For more information see [4], [5].

Support prediction

Curves

Surfaces

Implicitization

These results have been obtained using Maple 11 exact solving methods.

Curves

Surfaces

References

1 J. Rambau. TOPCOM: Triangulations of point configurations and oriented matroids. In A.M. Cohen, X.-S. Gao, and N. Takayama, editors, Math. Software: ICMS, pages 330–340. World Scientific, 2002.

2 I.Z.Emiris, V.Fisikopoulos, C.Konaxis, L.Peñaranda. An output-sensitive algorithm for computing projections of resultant polytopes. To appear in 28th Annual Symposium on Computational Geometry (SoCG 2012), Chapel Hill, NC, USA. (available from arXiv:1108.5985) http://arxiv.org/abs/1108.5985

3 I.Z.Emiris, V.Fisikopoulos, C.Konaxis, L.Peñaranda. ResPol: A software to compute a projection of the Newton polytope of the resultant, https://sourceforge.net/projects/respol/

4 I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011.

5 I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011. Submitted to journal.

6 This is the computation time of enumeration of regular triangulations algorithm using reverse search. We would like to thank very much Fumihiko TAKEUCHI for running the experiments and providing this results. Experiments were done on a Blade 100, 550Mhz, 2GB memory with SunOS 5.9.

7 This is the computation time of points2alltriangs client of TOPCOM package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.

8 This is the computation time of points2triangs client of TOPCOM package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.