Implicitization

From ErgaWiki

Contents 1 Implicitization experiments on curves and surfaces 2 Support prediction 3 Implicitization 4 References

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. We developed an output-sensitive algorithm for computing resultant polytopes and their projections [[EFKP]http://www.worldscientific.com/doi/abs/10.1142/S0218195913600108]. Its implementation, called ResPol can be found in [[Sourceforge]https://sourceforge.net/projects/respol/]. Let us demonstrate how to prepare the input for ResPol, given the parametric equations of the surface:

x = 1/2*s^2 - 1/2*t^2 - 1/4*s^4 + 3/2*s^2*t^2 - 1/4*t^4,
y = -s*t - s^3*t + s*t^3,
z = 2/3*s^3 - 2*s*t^2.

From the parametric expressions we define the following three polynomials:

F_1 = x- 1/2*s^2 + 1/2*t^2 + 1/4*s^4 - 3/2*s^2*t^2 + 1/4*t^4,
F_2 = y + s*t + s^3*t - s*t^3,
F_3 = z - 2/3*s^3 + 2*s*t^2.

Their supports with respect to the variables s,t are:

A_1 = [[0,0],[2,0],[0,2],[4,0],[2,2],[0,4]],

A_2 = [[0,0],[1,1],[3,1],[1,3]],

A_3 = [[0,0],[3,0],[1,2]].

The input to ResPol is as follows:

2
6 4 3 | 0 6 10
[[0,0],[2,0],[0,2],[4,0],[2,2],[0,4],[0,0],[1,1],[3,1],[1,3],[0,0],[3,0],[1,2]],

where the first line is the dimension of the supports (equal to the number of parameters), the second line contains the cardinalities of the supports and the elements of each support that are exponents of monomials whose coefficients contain an implicit variable (x,y, or z). In this example, these monomials correspond to the [0,0] point from each support. The latter define the projection of the resultant polytope thet ResPol computes. In the case of implicitization of polynomial parametric curves or surfaces, we can safely omit defining these points in the input file. Note that we number the elements in each support continuously starting from 0.

Then, Respol predicts the following vertices of the implicit polytope:

[3,2,2],[9,0,4],[0,12,0],[0,0,16],[4,4,0],[0,0,6],[8,4,0],[0,8,0],[3,0,4],[0,2,4],[3,2,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 inorder to obtain coefficients of the implicit equation.

For more information see [[EKK]http://ergawiki.di.uoa.gr/experiments/Implicitization-snc.pdf] link titleand [[EKK-TCS]http://ergawiki.di.uoa.gr/experiments/EBKKtcs11.pdf].

Support prediction

Curves

No	curve	parametric equation	supports	# mixed subdivisions	Enum by reverse search (sec) [6]	TOPCOM point2alltriang (sec) [7]	TOPCOM point2triang(sec) [8]	# mixed cell configurations	# N(R) vertices	N(R) vertices	# all lattice points of N(R)	implicit polytope's terms & coefficients	implicit support prediction (for curves)
1.	astroid	a\cos(t)^3,a\sin(t)^3	supports	289	193.62	0.048	0.452	289	35	N(R)	454	implicit	support
2.	cardioid	$a(2\cos(t)-\cos(2t)),a(2\sin(t)-\sin(2t))$	supports	37	6.52	0.005	0.024	37	10	N(R)	33	implicit	support
3.	circle	$ \cos(t),\sin(t)$	supports	5	0.004	0.016	0.004	5	3	N(R)	4	implicit	support
4.	conchoid	$a+\cos(t),a\tan(t)+\sin(t)$	supports	12	0.84	0.003	0.008	12	4	N(R)	6	implicit	support
5.	ellipse	$a\cos(t),b\sin(t)$	supports	5	0.15	0.001	0.004	5	3	N(R)	4	implicit	support
6.	folium of Descartes	$3at/(1+t^3),3at^2/(1+t^3)$	supports	14	0.94	0.004	0.008	14	6	N(R)	10	implicit	support
7.	involute of a circle	$a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$	supports	14	1.00	0.001	0.007	14	6	N(R)	7	implicit
8.	nephroid	$a(3\cos(t)-\cos(3t)),a(3\sin(t)-\sin(3t))$	supports	289	195.27	0.004	0.240	289	35	N(R)	454	implicit	support
9a.	Plateau curve	$a\sin(3t)/\sin(t),2a\sin(2t)$	supports	94	33.02	0.012	0.064	94	15	N(R)	55	implicit
9b.	plateau curve	$a\sin(6t)/ \sin(2t), 2a\sin(4t)$	supports	42168	halt	25.934	85.597	42168	495	N(R)	not computed	implicit
10.	talbot's curve	$(a^2 + c^2 \sin( t)^2) \cos( t)/a, (a^2 - 2c^2 + c^2\sin(t)^2)\sin(t)/b $	supports	1944	3948.80	0.416	2.356	1944	84	N(R)	1600	implicit
11.	tricuspoid	$a(2\cos(t)+\cos(2t)),a(2\sin(t)-\sin(2t))$	supports	37	6.20	0.008	0.024	37	10	N(R)	33	implicit	support
12.	witch of Agnesi	$at,a/(1 + t^2)$	supports	2	0.03	0.007	0.004	2	2	N(R)	2	implicit
13.	circle (3 systems)	$(-t^2 +1)/s, 2t/s, t^2 -s +1$	supports	26	6.00	0.020	0.052	26	6	N(R)	7	implicit
14.	A' Campo curve	$9ts-4,t^3+s^2+c1,t^2+s^3+c2$	supports	29	-	-	-	29	6	N(R)	18	implicit

Surfaces

No	surface	parametric equation	supports	# mixed subdivisions	Enum by reverse search (sec)	TOPCOM point2alltriang (sec)	TOPCOM point2triang(sec)	# mixed cell configurations	# N(R) vertices	N(R) vertices	# all lattice points of N(R)	implicit polytope's terms & coefficients
1.	cylinder	$\cos(t),\sin(t),s$	supports	5	0.24	0.003	0.006	5	3	N(R)	4	implicit
2.	cone	$s\cos(t),s\sin(t),s$	supports	122	73.45	0.192	0.288	98	8	N(R)	14	implicit
3.	paraboloid	$s\cos(t),s\sin(t),s^2$	supports	122	71.60	0.192	0.296	98	8	N(R)	37	implicit
4.	surface of revolution	$s\cos(t),s\sin(t),\cos(s)$	supports	122	71.80	0.193	0.288	98	8	N(R)	37	implicit
5.	sphere	$\sin(t)\cos(s),\sin(t)\sin(s),\cos(t)$	supports	104148	halt	19496.602	714.161	43018	21	N(R)	186	implicit
6.	sphere2	$\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)$	supports	76280	halt	4492.977	397.157	32076	95	N(R)	776	implicit
7.	stereographic sphere	$2t/(1 t^2 s^2),2s/(1 t^2 s^2),(t^2 s^2-1)/(1 t^2 s^2)$	supports	3540	7112.54	25.402	11.025	3126	22	N(R)	283	implicit
8.	twisted sphere	$a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$	supports	>1812221	not computed	not computed	not computed	not computed	not computed		not computed	implicit

Implicitization

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

Curves

No	curve	parametric degree	parametric terms	"curves only" matrix size	"curves only" method runtime (sec)	generic method: matrix size	generic method runtime (sec)	generic method nonzero coeffs	"mapping" method: matrix size	"mapping" method runtime (sec)	"mapping" method nonzero coeffs (actual coeffs)	implicit degree
	1.	cardioid	4, 4	3, 4	15	0.128	33	0.248	33	25	0.656	7	4
2.	conhoid	2, 3	2, 4	15	0.094	6	0.096	6	15	0.308	6	4
3.	folium of descartes	3, 3	3, 3	10	0.092	5	0.032	3	11	0.144	3	3
4.	nephroid	4, 4	4, 5	28	0.256	426	not computed	not computed	49	5.452	10	6
5.	ranunculoid	12, 12	7, 12	91	8809.43	not computed	not computed	not computed	not computed	not computed	not computed	not computed
6.	talbot's curve	6, 6	3, 4	28	109.342	421	not computed	not computed	not computed	not computed	23	6
7.	tricuspoid	4, 4	3, 4	15	0.216	33	0.236	33	25	0.540	8	4
8.	whitch of agnesi	1, 2	2, 2	4	0.016	2	0.044	2	4	0.048	3	3

Surfaces

No	surface	parametric degree	parametric terms	# inside points	generic method: matrix size	generic method runtime (sec)	generic method nonzero coeffs	"mapping" method: matrix size	"mapping" method runtime (sec)	"mapping" method nonzero coeffs (actual coeffs)	implicit degree
1.	Infinite cylinder	2, 2, 1	2, 3, 2	4	4	0.036	4	9	0.072	3	2
2.	Hyperbolic paraboloid	1, 1, 2	2, 2, 3	3	3	0.028	3	7	0.064	3	2
3.	Infinite cone	3, 2, 1	4, 3, 2	14	8	0.040	6	19	0.224	3	4
4.	Whitney umbrella	2, 1, 2	2, 2, 2	2	2	0.024	2	4	0.056	2	3
5.	Monkey saddle	1, 1, 3	2, 2, 3	3	3	0.028	3	8	0.064	3	3
6.	Handkerchief surface	1, 1, 3	2, 2, 5	2	2	0.020	2	4	0.036	5	3
7.	Crossed surface	1, 1, 4	2, 2, 2	5	5	0.032	5	10	0.072	2	4
8.	Quartoid	1, 1, 4	2, 2, 4	4	4	0.012	4	16	0.140	4	4
9.	Peano surface	1, 1, 4	2, 2, 4	4	4	0.020	4	10	0.080	4	4
10.	Bohemian dome	2, 4, 2	2, 6, 3	142	58	2.764	error	125	83.362	7	4
11.	Swallowtail surface	4, 3, 1	3, 3, 2	12	12	0.052	12	25	0.432	6	5
12.	Sine surface	2, 2, 4	3, 3, 8	1027	87	9.244	66	125	107.102	7	6
13.	Enneper's surface	3, 3, 2	4, 3, 3	439	258	74.304	258	106	33.562	57	9

References

1 I.Z.Emiris, V.Fisikopoulos, C.Konaxis, L.Peñaranda. An oracle-based, output sensitive algorithm for projections of resultant polytopes. International Journal of Computational Geometry and Applications vol. 23, pp. 397-423, (Special issue) [World Scientific[1]] 2013.

2 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/

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

4 I. Z. Emiris, T. Kalinka, Ch. Konaxis, T. Luu Ba, Implicitization of curves and surfaces using predicted support, 2011. Theor. Comp. Sci..

6 This is the computation time of enumeration of regular triangulations algorithm using reverse search. We would like to thank Fumihiko TAKEUCHI for running the experiments and providing the 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.