View source

=== 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 <ref> Fisikopoulos Vissarion, Triangulations of point sets, high dimensional Polytopes and
Applications, Master thesis, University of Athens, Graduate Program in Logic, Algorithms and Computation, 2010 [http://cgi.di.uoa.gr/~vfisikop/projects/msc_thesis.pdf] </ref>.

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''. [http://ergawiki.di.uoa.gr/experiments/i2D.mpl Code] and some [http://ergawiki.di.uoa.gr/experiments/i2Dexamples.mw examples]. For more information see <ref> 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>.

== Support prediction ==
'''Curves'''
{| class="experiments sortable" 
!   No
! class="unsortable" | curve <ref> Many thanks to Tatjana Kalinka for providing this list of curves and surfaces. </ref>
! class="unsortable" | parametric equation 
! class="unsortable" | supports
! <nowiki># mixed subdivisions</nowiki>
! class="run" |
Enum by reverse search (sec) <ref> This is the computation time of [http://jn.wspc.com.sg/google/pdf/S0218195902000980.pdf  enumeration of regular triangulations algorithm using reverse search]. I 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) <ref> 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) <ref> 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>
! class="unsortable" | <nowiki>N(R) vertices</nowiki>
! class="unsortable" | <nowiki># all lattice points of N(R)</nowiki>
! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki>
! class="unsortable" | <nowiki> implicit support prediction (for curves)</nowiki>
|-
|
|-
| 1.
| astroid
|a\cos(t)^3,a\sin(t)^3 
|
[http://ergawiki.di.uoa.gr/curves_supports/supports1.dat supports]
| class="topcom" | 289
| 193.62
| 0.048
| 0.452
| 289
| 35
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res1.dat N(R)]
| 454
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_1.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_1.dat support]
|-
| 2.
| cardioid
| $a(2\cos(t)-\cos(2t)),a(2\sin(t)-\sin(2t))$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports2.dat supports]
| class="topcom" | 37
| 6.52
| 0.005
| 0.024
| 37
| 10
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res2.dat N(R)]
| 33
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_2.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_2.dat support]
|-
| 3.
| circle
|$ \cos(t),\sin(t)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports3.dat supports]
| class="topcom" | 5
| 0.004
| 0.016
| 0.004
| 5
| 3
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res3.dat N(R)]
| 4
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_3.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_3.dat support]
|-
| 4.
| conchoid
| $a+\cos(t),a\tan(t)+\sin(t)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports4.dat supports]
| class="topcom" | 12
| 0.84
| 0.003
| 0.008
| 12
| 4
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res4.dat N(R)]
| 6
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_4.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_4.dat support]
|-
| 5.
| ellipse
| $a\cos(t),b\sin(t)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports5.dat supports]
| class="topcom" | 5
| 0.15
| 0.001
| 0.004
| 5
| 3
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res5.dat N(R)]
| 4
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_5.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_5.dat support]
|-
| 6.
| folium of Descartes
| $3at/(1+t^3),3at^2/(1+t^3)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports6.dat supports]
| class="topcom" | 14
| 0.94
| 0.004
| 0.008
| 14
| 6
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res6.dat N(R)]
| 10
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_6.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_6.dat support]
|-
| 7.
| involute of a circle
| $a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports7.dat supports]
| class="topcom" | 14
| 1.00
| 0.001
| 0.007
| 14
| 6
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res7.dat N(R)]
| 7
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_7.html implicit]
|
|-
| 8.
| nephroid
| $a(3\cos(t)-\cos(3t)),a(3\sin(t)-\sin(3t))$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports8.dat supports]
| class="topcom" | 289
| 195.27
| 0.004
| 0.240
| 289
| 35
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res8.dat N(R)]
| 454
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_8.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_8.dat support]
|-
| 9a.
| Plateau curve
| $a\sin(3t)/\sin(t),2a\sin(2t)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports9a.dat supports]
| class="topcom" | 94
| 33.02
| 0.012
| 0.064
| 94
| 15
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9a.dat N(R)]
| 55
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9a.html implicit]
|
|-
| 9b.
| plateau curve
| $a\sin(6t)/ \sin(2t), 2a\sin(4t)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports9b.dat supports]
| class="topcom" | 42168
| class="halt" | halt
| 25.934
| 85.597
| 42168
| 495
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9b.dat N(R)]
| class="halt" | not computed
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9b.html 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 $
|
[http://ergawiki.di.uoa.gr/curves_supports/supports10.dat supports]
| class="topcom" | 1944
| 3948.80
| 0.416
| 2.356
| 1944
| 84
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res10.dat N(R)]
| 1600
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_10.html implicit]
|
|-
| 11.
| tricuspoid
| $a(2\cos(t)+\cos(2t)),a(2\sin(t)-\sin(2t))$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports11.dat supports]
| class="topcom" | 37
| 6.20
| 0.008
| 0.024
| 37
| 10
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res11.dat N(R)]
| 33
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_11.html implicit]
| [http://ergawiki.di.uoa.gr/impl_sup/impl_support_11.dat support]
|-
| 12.
| witch of Agnesi
| $at,a/(1 + t^2)$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports12.dat supports]
| class="topcom" | 2
| 0.03
| 0.007
| 0.004
| 2
| 2
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res12.dat N(R)]
| 2
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_12.html implicit]
|
|-
| 13.
| circle (3 systems)
| $(-t^2 +1)/s, 2t/s, t^2 -s +1$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports13.dat supports]
| class="topcom" | 26
| 6.00
| 0.020
| 0.052
| 26
| 6
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res13.dat N(R)]
| 7
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_13.html implicit]
|
|-
| 14.
| A' Campo curve
| $9ts-4,t^3+s^2+c1,t^2+s^3+c2$
|
[http://ergawiki.di.uoa.gr/curves_supports/supports14.dat supports]
| class="topcom" | 29
| -
| -
| -
| 29
| 6
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res14.dat N(R)]
| 18
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_14.html implicit]
|
|}

'''Surfaces''' 
{|class="experiments sortable"
! No
! surface
! class="unsortable" | parametric equation
! class="unsortable" | supports
! <nowiki># mixed subdivisions</nowiki>
! class="run" |
Enum by reverse search (sec)
! class="run" |
TOPCOM point2alltriang (sec)
! class="run" |
TOPCOM point2triang(sec)
! <nowiki># mixed cell configurations</nowiki>
! class="unsortable" | <nowiki># N(R) vertices</nowiki>
! class="unsortable" | <nowiki>N(R) vertices</nowiki>
! class="unsortable" | <nowiki># all lattice points of N(R)</nowiki>
! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki>
|-
|
|-
| 1.
| cylinder
| $\cos(t),\sin(t),s$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports1.dat supports]
| class="topcom" | 5
| 0.24
| 0.003
| 0.006
| 5
| 3
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res1.dat N(R)]
| 4
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_1.html implicit]
|-
| 2.
| cone
| $s\cos(t),s\sin(t),s$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports2.dat supports]
| class="topcom" | 122
| 73.45
| 0.192
| 0.288
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res2.dat N(R)]
| 14
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_2.html implicit]
|-
| 3.
| paraboloid
| $s\cos(t),s\sin(t),s^2$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports3.dat supports]
| class="topcom" | 122
| 71.60
| 0.192
| 0.296
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res3.dat N(R)]
| 37
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_3.html implicit]
|-
| 4.
| surface of revolution
| $s\cos(t),s\sin(t),\cos(s)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports4.dat supports]
| class="topcom" | 122
| 71.80
| 0.193
| 0.288
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res4.dat N(R)]
| 37
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_4.html implicit]
|-
| 5.
| sphere
| $\sin(t)\cos(s),\sin(t)\sin(s),\cos(t)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports5.dat supports]
| class="topcom" | 104148
| class="halt" | halt
| 19496.602
| 714.161
| 43018
| 21
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res5.dat N(R)]
| 186
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_5.html implicit]
|-
| 6.
| sphere2
| $\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports6.dat supports]
| class="topcom" | 76280
| class="halt" | halt
| 4492.977
| 397.157
| 32076
| 95
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res6.dat N(R)]
| 776
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_6.html 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)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports7.dat supports]
| class="topcom" | 3540
| 7112.54
| 25.402
| 11.025
| 3126
| 22
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res7.dat N(R)]
| 283
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_7.html implicit]
|-
| 8.
| twisted sphere
| $a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports8.dat supports]
| class="topcom" | &gt;1812221
| class="halt"  | not computed
| class="halt" | not computed
| class="halt" | not computed
| class="halt" | not computed
| class="halt" | not computed
|
| class="halt" | not computed
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_8.html implicit]
|}

== Implicitization ==
This results have been obtained using Maple 11 exact solving methods.
{|class="experiments sortable"
! No
! surface
! class="unsortable" | parametric equation
! class="unsortable" | supports
! <nowiki># mixed subdivisions</nowiki>
! class="run" |
Enum by reverse search (sec)
! class="run" |
TOPCOM point2alltriang (sec)
! class="run" |
TOPCOM point2triang(sec)
! <nowiki># mixed cell configurations</nowiki>
! class="unsortable" | <nowiki># N(R) vertices</nowiki>
! class="unsortable" | <nowiki>N(R) vertices</nowiki>
! class="unsortable" | <nowiki># all lattice points of N(R)</nowiki>
! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki>
|-
|
|-
| 1.
| cylinder
| $\cos(t),\sin(t),s$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports1.dat supports]
| class="topcom" | 5
| 0.24
| 0.003
| 0.006
| 5
| 3
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res1.dat N(R)]
| 4
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_1.html implicit]
|-
| 2.
| cone
| $s\cos(t),s\sin(t),s$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports2.dat supports]
| class="topcom" | 122
| 73.45
| 0.192
| 0.288
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res2.dat N(R)]
| 14
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_2.html implicit]
|-
| 3.
| paraboloid
| $s\cos(t),s\sin(t),s^2$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports3.dat supports]
| class="topcom" | 122
| 71.60
| 0.192
| 0.296
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res3.dat N(R)]
| 37
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_3.html implicit]
|-
| 4.
| surface of revolution
| $s\cos(t),s\sin(t),\cos(s)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports4.dat supports]
| class="topcom" | 122
| 71.80
| 0.193
| 0.288
| 98
| 8
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res4.dat N(R)]
| 37
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_4.html implicit]
|-
| 5.
| sphere
| $\sin(t)\cos(s),\sin(t)\sin(s),\cos(t)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports5.dat supports]
| class="topcom" | 104148
| class="halt" | halt
| 19496.602
| 714.161
| 43018
| 21
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res5.dat N(R)]
| 186
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_5.html implicit]
|-
| 6.
| sphere2
| $\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports6.dat supports]
| class="topcom" | 76280
| class="halt" | halt
| 4492.977
| 397.157
| 32076
| 95
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res6.dat N(R)]
| 776
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_6.html 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)$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports7.dat supports]
| class="topcom" | 3540
| 7112.54
| 25.402
| 11.025
| 3126
| 22
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res7.dat N(R)]
| 283
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_7.html implicit]
|-
| 8.
| twisted sphere
| $a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$
|
[http://ergawiki.di.uoa.gr/surfaces_supports/supports8.dat supports]
| class="topcom" | &gt;1812221
| class="halt"  | not computed
| class="halt" | not computed
| class="halt" | not computed
| class="halt" | not computed
| class="halt" | not computed
|
| class="halt" | not computed
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_8.html implicit]
|}

== 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 [http://cgi.di.uoa.gr/~vfisikop/projects/msc_thesis.pdf]

[2] 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]

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

[4] This is the computation time of [http://jn.wspc.com.sg/google/pdf/S0218195902000980.pdf  enumeration of regular triangulations algorithm using reverse search]. I 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.

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

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