Implicitization

From ErgaWiki

(Difference between revisions)

Revision as of 11:12, 5 March 2012

Implicitization is the change of parametric representation 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 circle below is given parametrically by x=cos(t), y=sin(t); its implicit equation is x^2+y^2=1.

For the case of curves, there are two equations in one parameter t. For the case of surfaces, there are 3 expressions in two parameters t,s. Additionally, in certain parameterizations, we consider families of curves/surfaces with respect to free constants a,b,c. Each parametric expression can be transformed to a polynomial. We consider the system of polynomials in the parameters and define its sparse resultant. We compute the resultant's Newton polytope, which gives information on the implicit equation's support. Then, we compute the implicit equation by interpolation, which amounts to linear algebra.

The first section contains experimental results on support prediction step which is the computation of the Newton polytope of the sparse resultant, the resultant polytope, given the system of polynomials constructed by the parametric expressions. 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. The method used here retrieve 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 has much more vertices that the resultant polytope as shown in the experiments below. To overcome the inefficiency of computing the secondary polytope an output-sensitive algorithm for computing resultant polytopes and its projections has been proposed in ^[2]. Its implementation can be found in ^[3]. For experimental results of this method see ^[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 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 ^[4].

References

↑ 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.0 ^2.1 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
↑ 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/
↑ I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011 [1]

Support prediction

Curves

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