Implicitization

From ErgaWiki

(Difference between revisions)

Current revision as of 22:14, 14 December 2015

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 in order to obtain coefficients of the implicit equation.

For background information see [[EKKL-TCS]http://ergawiki.di.uoa.gr/experiments/EBKKtcs11.pdf]. For recent progress see [[EKK2015]http://www.sciencedirect.com/science/article/pii/S1524070315000260].

Implicitization experiments

These are (outdated) results 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

Support prediction experiments

Curves

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

Footnotes:

1 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.

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

3 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.

Implicitization

From ErgaWiki

Current revision as of 22:14, 14 December 2015

Implicitization experiments on curves and surfaces

Implicitization experiments

Support prediction experiments

Views

Personal tools

Navigation

Search

Toolbox

@@ Line 3: / Line 3: @@
 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.
+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.
-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.
+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.
-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.
+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].
-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.
+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:
-The method used here retrieves the resultant polytope from the computation of another polytope called secondary polytope.
-We use TOPCOM [1]
-<!--
-<ref name="topcom"> 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. </ref>
--->
-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].
-<!--
-<ref name="socg12"> 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</ref>.
--->
-Its implementation, called ResPol can be found in [3].
-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,<br>
@@ Line 60: / Line 41: @@
 [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''.
-<ref name="respol">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/</ref>. For experimental results of this method see [2].
+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 [http://ergawiki.di.uoa.gr/experiments/simpl.mpl '''''Maple'' implementation'''] of the implicitization with predicted support and some [http://ergawiki.di.uoa.gr/experiments/examples.mw examples]. Here we apply numeric (SVD) as well as exact methods for linear solving in order to obtain coefficients of the implicit equation.
--->
-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  [http://ergawiki.di.uoa.gr/experiments/implicitization.mpl ''Maple'' implementation] of the implicitization with predicted support and some [http://ergawiki.di.uoa.gr/experiments/implicitization_examples.mw 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],
+For background information see [[EKKL-TCS]http://ergawiki.di.uoa.gr/experiments/EBKKtcs11.pdf]. For recent progress see [[EKK2015]http://www.sciencedirect.com/science/article/pii/S1524070315000260].
-<!--<ref name="EKK"> I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011 [http://ergawiki.di.uoa.gr/experiments/Implicitization-snc.pdf] </ref>.
--->
-[5].
-<!--<ref name="EKK"> I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011. Submitted to journal. [http://ergawiki.di.uoa.gr/experiments/EBKKtcs11.pdf] </ref>.
--->
-== Support prediction ==
+== Implicitization experiments ==
+These are (outdated) results obtained using Maple 11 exact solving methods.
+'''Curves'''
+{|class="experiments sortable"
+! No
+! curve
+! class="unsortable" | parametric degree
+! class="unsortable" | parametric terms
+! "curves only" matrix size
+! class="run" |
+"curves only" method runtime (sec)
+! generic method: matrix size
+! class="run" |
+generic method runtime (sec)
+! generic method nonzero coeffs
+! "mapping" method: matrix size
+! class="run" |
+"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
+| class="halt" | not computed
+| class="halt" | not computed
+| 49
+| 5.452
+| 10
+| 6
+|-
+| 5.
+| ranunculoid
+| 12, 12
+| 7, 12
+| 91
+| 8809.43
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+|-
+| 6.
+| talbot's curve
+| 6, 6
+| 3, 4
+| 28
+| 109.342
+| 421
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | not computed
+| class="halt" | 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'''
+{|class="experiments sortable"
+! No
+! surface
+! class="unsortable" | parametric degree
+! class="unsortable" | parametric terms
+! # inside points
+! generic method: matrix size
+! class="run" |
+generic method runtime (sec)
+! generic method nonzero coeffs
+! "mapping" method: matrix size
+! class="run" |
+"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
+| class="halt" | 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
+|-
+|}
+== Support prediction experiments ==
 '''Curves'''
@@ Line 83: / Line 388: @@
 ! <nowiki># mixed subdivisions</nowiki>
 ! class="run" |
-Enum by reverse search (sec) [6] <!-- <ref name="test1"> This is the computation time of [http://jn.wspc.com.sg/google/pdf/S0218195902000980.pdf  enumeration of regular triangulations algorithm using reverse search]. We would like to thank very much [http://www.purple.dti.ne.jp/pub/cv.html  Fumihiko TAKEUCHI] for running the experiments and providing this results. Experiments were done on a Blade 100, 550Mhz, 2GB memory with SunOS 5.9.</ref>-->
+Enum by reverse search (sec) [1] <!-- <ref name="test1"> This is the computation time of [http://jn.wspc.com.sg/google/pdf/S0218195902000980.pdf  enumeration of regular triangulations algorithm using reverse search]. We would like to thank very much [http://www.purple.dti.ne.jp/pub/cv.html  Fumihiko TAKEUCHI] for running the experiments and providing this results. Experiments were done on a Blade 100, 550Mhz, 2GB memory with SunOS 5.9.</ref>-->
 ! class="run" |
-TOPCOM point2alltriang (sec) [7] <!--<ref name="test2"> This is the computation time of '''points2alltriangs''' client of [http://www.rambau.wm.uni-bayreuth.de/TOPCOM/ TOPCOM] package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.</ref> -->
+TOPCOM point2alltriang (sec) [2] <!--<ref name="test2"> This is the computation time of '''points2alltriangs''' client of [http://www.rambau.wm.uni-bayreuth.de/TOPCOM/ TOPCOM] package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.</ref> -->
 ! class="run" |
-TOPCOM point2triang(sec) [8] <!-- <ref  name="test3"> This is the computation time of '''points2triangs''' client of [http://www.rambau.wm.uni-bayreuth.de/TOPCOM/ TOPCOM] package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.</ref> -->
+TOPCOM point2triang(sec) [3] <!-- <ref  name="test3"> This is the computation time of '''points2triangs''' client of [http://www.rambau.wm.uni-bayreuth.de/TOPCOM/ TOPCOM] package. Experiments were done on a Intel(R) Pentium(R) 4 CPU 3.20GHz, 1.5GB memory with x86_64 Debian GNU/Linux.</ref> -->
 ! class="unsortable" | <nowiki># mixed cell configurations</nowiki>
 ! class="unsortable" | <nowiki># N(R) vertices</nowiki>
@@ Line 480: / Line 785: @@
 |}
-== Implicitization ==
+Footnotes:
-These results have been obtained using Maple 11 exact solving methods.
-'''Curves'''
-{|class="experiments sortable"
-! No
-! curve
-! class="unsortable" | parametric degree
-! class="unsortable" | parametric terms
-! "curves only" matrix size
-! class="run" |
-"curves only" method runtime (sec)
-! generic method: matrix size
-! class="run" |
-generic method runtime (sec)
-! generic method nonzero coeffs
-! "mapping" method: matrix size
-! class="run" |
-"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
-| class="halt" | not computed
-| class="halt" | not computed
-| 49
-| 5.452
-| 10
-| 6
-|-
-| 5.
-| ranunculoid
-| 12, 12
-| 7, 12
-| 91
-| 8809.43
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-|-
-| 6.
-| talbot's curve
-| 6, 6
-| 3, 4
-| 28
-| 109.342
-| 421
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | not computed
-| class="halt" | 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'''
-{|class="experiments sortable"
-! No
-! surface
-! class="unsortable" | parametric degree
-! class="unsortable" | parametric terms
-! # inside points
-! generic method: matrix size
-! class="run" |
-generic method runtime (sec)
-! generic method nonzero coeffs
-! "mapping" method: matrix size
-! class="run" |
-"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
-| class="halt" | 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==
-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.
-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, [http://ergawiki.di.uoa.gr/experiments/Impl2011.pdf Implicitization of curves and surfaces using predicted support, 2011].
-I. Z. Emiris, T. Kalinka, Ch. Konaxis, [http://ergawiki.di.uoa.gr/experiments/EBKK11.pdf Implicitization of curves and surfaces using predicted support, 2011. Submitted to journal].
-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.
+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.
 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.
 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.