Implicitization

From ErgaWiki

(Difference between revisions)
Jump to: navigation, search
(→Curves)
(→Implicitization experiments on curves and surfaces)
Line 13: Line 13:
!  No
!  No
! class="unsortable" | curve <ref> Many thanks to Tatjana Kalinka for providing this list of curves and surfaces. </ref>
! class="unsortable" | curve <ref> Many thanks to Tatjana Kalinka for providing this list of curves and surfaces. </ref>
-
! class="unsortable" | equation  
+
! class="unsortable" | parametric equation  
! class="unsortable" | supports
! class="unsortable" | supports
! <nowiki># mixed subdivisions</nowiki>
! <nowiki># mixed subdivisions</nowiki>
Line 26: Line 26:
! 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># all lattice points of N(R)</nowiki>
 +
! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki>
|-
|-
|
|
Line 42: Line 43:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res1.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res1.dat N(R)]
| 454
| 454
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_1.html implicit]
|-
|-
| 2.
| 2.
Line 56: Line 58:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res2.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res2.dat N(R)]
| 33
| 33
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_2.html implicit]
|-
|-
| 3.
| 3.
Line 70: Line 73:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res3.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res3.dat N(R)]
| 4
| 4
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_3.html implicit]
|-
|-
| 4.
| 4.
Line 84: Line 88:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res4.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res4.dat N(R)]
| 6
| 6
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_4.html implicit]
|-
|-
| 5.
| 5.
Line 98: Line 103:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res5.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res5.dat N(R)]
| 4
| 4
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_5.html implicit]
|-
|-
| 6.
| 6.
Line 112: Line 118:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res6.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res6.dat N(R)]
| 10
| 10
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_6.html implicit]
|-
|-
| 7.
| 7.
Line 126: Line 133:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res7.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res7.dat N(R)]
| 7
| 7
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_7.html implicit]
|-
|-
| 8.
| 8.
Line 140: Line 148:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res8.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res8.dat N(R)]
| 454
| 454
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_8.html implicit]
|-
|-
| 9a.
| 9a.
Line 154: Line 163:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9a.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9a.dat N(R)]
| 55
| 55
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9a.html implicit]
|-
|-
| 9b.
| 9b.
Line 168: Line 178:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9b.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res9b.dat N(R)]
| class="halt" | not computed
| class="halt" | not computed
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9b.html implicit]
|-
|-
| 10.
| 10.
Line 182: Line 193:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res10.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res10.dat N(R)]
| 1600
| 1600
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_10.html implicit]
|-
|-
| 11.
| 11.
Line 196: Line 208:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res11.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res11.dat N(R)]
| 33
| 33
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_11.html implicit]
|-
|-
| 12.
| 12.
Line 210: Line 223:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res12.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res12.dat N(R)]
| 2
| 2
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_12.html implicit]
|-
|-
| 13.
| 13.
Line 224: Line 238:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res13.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res13.dat N(R)]
| 7
| 7
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_13.html implicit]
|-
|-
| 14.
| 14.
Line 238: Line 253:
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res14.dat N(R)]
| [http://ergawiki.di.uoa.gr/curves_res_extreme/res14.dat N(R)]
| 18
| 18
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_14.html implicit]
|}
|}
Line 244: Line 260:
! No
! No
! surface
! surface
-
! class="unsortable" | equation
+
! class="unsortable" | parametric equation
! class="unsortable" | supports
! class="unsortable" | supports
! <nowiki># mixed subdivisions</nowiki>
! <nowiki># mixed subdivisions</nowiki>
Line 257: Line 273:
! 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># all lattice points of N(R)</nowiki>
 +
! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki>
|-
|-
|
|
Line 273: Line 290:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res1.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res1.dat N(R)]
| 4
| 4
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_1.html implicit]
|-
|-
| 2.
| 2.
Line 287: Line 305:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res2.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res2.dat N(R)]
| 14
| 14
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_2.html implicit]
|-
|-
| 3.
| 3.
Line 301: Line 320:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res3.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res3.dat N(R)]
| 37
| 37
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_3.html implicit]
|-
|-
| 4.
| 4.
Line 315: Line 335:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res4.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res4.dat N(R)]
| 37
| 37
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_4.html implicit]
|-
|-
| 5.
| 5.
Line 329: Line 350:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res5.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res5.dat N(R)]
| 186
| 186
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_5.html implicit]
|-
|-
| 6.
| 6.
Line 343: Line 365:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res6.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res6.dat N(R)]
| 776
| 776
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_6.html implicit]
|-
|-
| 7.
| 7.
Line 357: Line 380:
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res7.dat N(R)]
| [http://ergawiki.di.uoa.gr/surfaces_res_extreme/res7.dat N(R)]
| 283
| 283
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_7.html implicit]
|-
|-
| 8.
| 8.
Line 371: Line 395:
|
|
| class="halt" | not computed
| class="halt" | not computed
 +
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_surf_8.html implicit]
|}
|}

Revision as of 13:20, 16 March 2010

Contents

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.


Curves

No curve [2] parametric equation supports # mixed subdivisions

Enum by reverse search (sec) [3]

TOPCOM point2alltriang (sec) [4]

TOPCOM point2triang(sec) [5]

# mixed cell configurations # N(R) vertices N(R) vertices # all lattice points of N(R) implicit polytope's terms & coefficients
1. astroid a\cos(t)^3,a\sin(t)^3

supports

289 193.62 0.048 0.452 289 35 N(R) 454 implicit
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
3. circle $ \cos(t),\sin(t)$

supports

5 0.004 0.016 0.004 5 3 N(R) 4 implicit
4. conchoid $a+\cos(t),a\tan(t)+\sin(t)$

supports

12 0.84 0.003 0.008 12 4 N(R) 6 implicit
5. ellipse $a\cos(t),b\sin(t)$

supports

5 0.15 0.001 0.004 5 3 N(R) 4 implicit
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
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
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
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 shpere $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 shpere $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

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. ↑ Many thanks to Tatjana Kalinka for providing this list of curves and surfaces.
  3. ↑ 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.
  4. ↑ 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.
  5. ↑ 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.
Retrieved from "http://ergawiki.di.uoa.gr/index.php/Implicitization"
Personal tools