Implicitization

From ErgaWiki

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

Implicitization experiments on curves and surfaces

These are some experimental results of the algorithms that compute the Newton polytope of the Resultant. For more information see ^[1].

For the case of curves, there are two equations on one variable t. For the case of surfaces, there are three equations on two variables t,s. Additionally, a,b,c are constants.

Each parametric equation can be transformed to a polynomial. The supports of the polynomials after 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.

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

Another Maple implementation contains two implicitization methods for general support prediction that use exact solving. Examples of running these methods on the curves and surfaces.

For more information see ^[2].

Support prediction

Curves

No	curve [3]	parametric equation	supports	# mixed subdivisions	Enum by reverse search (sec) [4]	TOPCOM point2alltriang (sec) [5]	TOPCOM point2triang(sec) [6]	# 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		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

Remarks

[1] Fisikopoulos Vissarion, Triangulations of point sets, high dimensional Polytopes and Applications, Master thesis, University of Athens, Graduate Program in Logic, Algorithms and Computation, 2010 [1]

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

[3] Many thanks to Tatjana Kalinka for providing this list of curves and surfaces.

[4] This is the computation time of enumeration of regular triangulations algorithm using reverse search. I 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.

[5] 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.

[6] 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.