Implicitization
From ErgaWiki
(Difference between revisions)
(→Implicitization experiments on curves and surfaces) |
(→Curves) |
||
| Line 27: | Line 27: | ||
! 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> | ! class="unsortable" | <nowiki> implicit polytope's terms & coefficients</nowiki> | ||
| + | ! class="unsortable" | <nowiki> implicit support prediction (for curves)</nowiki> | ||
|- | |- | ||
| | | | ||
| Line 44: | Line 45: | ||
| 454 | | 454 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_1.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_1.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_1.dat support] | ||
|- | |- | ||
| 2. | | 2. | ||
| Line 59: | Line 61: | ||
| 33 | | 33 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_2.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_2.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_2.dat support] | ||
|- | |- | ||
| 3. | | 3. | ||
| Line 74: | Line 77: | ||
| 4 | | 4 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_3.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_3.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_3.dat support] | ||
|- | |- | ||
| 4. | | 4. | ||
| Line 89: | Line 93: | ||
| 6 | | 6 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_4.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_4.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_4.dat support] | ||
|- | |- | ||
| 5. | | 5. | ||
| Line 104: | Line 109: | ||
| 4 | | 4 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_5.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_5.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_5.dat support] | ||
|- | |- | ||
| 6. | | 6. | ||
| Line 119: | Line 125: | ||
| 10 | | 10 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_6.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_6.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_6.dat support] | ||
|- | |- | ||
| 7. | | 7. | ||
| Line 134: | Line 141: | ||
| 7 | | 7 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_7.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_7.html implicit] | ||
| + | | | ||
|- | |- | ||
| 8. | | 8. | ||
| Line 149: | Line 157: | ||
| 454 | | 454 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_8.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_8.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_8.dat support] | ||
|- | |- | ||
| 9a. | | 9a. | ||
| Line 164: | Line 173: | ||
| 55 | | 55 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9a.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_9a.html implicit] | ||
| + | | | ||
|- | |- | ||
| 9b. | | 9b. | ||
| Line 179: | Line 189: | ||
| class="halt" | not computed | | class="halt" | not computed | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_9b.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_9b.html implicit] | ||
| + | | | ||
|- | |- | ||
| 10. | | 10. | ||
| Line 194: | Line 205: | ||
| 1600 | | 1600 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_10.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_10.html implicit] | ||
| + | | | ||
|- | |- | ||
| 11. | | 11. | ||
| Line 209: | Line 221: | ||
| 33 | | 33 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_11.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_11.html implicit] | ||
| + | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_11.dat support] | ||
|- | |- | ||
| 12. | | 12. | ||
| Line 224: | Line 237: | ||
| 2 | | 2 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_12.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_12.html implicit] | ||
| + | | | ||
|- | |- | ||
| 13. | | 13. | ||
| Line 239: | Line 253: | ||
| 7 | | 7 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_13.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_13.html implicit] | ||
| + | | | ||
|- | |- | ||
| 14. | | 14. | ||
| Line 254: | Line 269: | ||
| 18 | | 18 | ||
| [http://ergawiki.di.uoa.gr/implicit_equation/impl_14.html implicit] | | [http://ergawiki.di.uoa.gr/implicit_equation/impl_14.html implicit] | ||
| + | | | ||
|} | |} | ||
Revision as of 18:07, 26 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 | implicit support prediction (for curves) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1. | astroid | a\cos(t)^3,a\sin(t)^3 | 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))$ | 37 | 6.52 | 0.005 | 0.024 | 37 | 10 | N(R) | 33 | implicit | support | |
| 3. | circle | $ \cos(t),\sin(t)$ | 5 | 0.004 | 0.016 | 0.004 | 5 | 3 | N(R) | 4 | implicit | support | |
| 4. | conchoid | $a+\cos(t),a\tan(t)+\sin(t)$ | 12 | 0.84 | 0.003 | 0.008 | 12 | 4 | N(R) | 6 | implicit | support | |
| 5. | ellipse | $a\cos(t),b\sin(t)$ | 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)$ | 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))$ | 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))$ | 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)$ | 94 | 33.02 | 0.012 | 0.064 | 94 | 15 | N(R) | 55 | implicit | ||
| 9b. | plateau curve | $a\sin(6t)/ \sin(2t), 2a\sin(4t)$ | 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 $ | 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))$ | 37 | 6.20 | 0.008 | 0.024 | 37 | 10 | N(R) | 33 | implicit | support | |
| 12. | witch of Agnesi | $at,a/(1 + t^2)$ | 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$ | 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$ | 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$ | 5 | 0.24 | 0.003 | 0.006 | 5 | 3 | N(R) | 4 | implicit | |
| 2. | cone | $s\cos(t),s\sin(t),s$ | 122 | 73.45 | 0.192 | 0.288 | 98 | 8 | N(R) | 14 | implicit | |
| 3. | paraboloid | $s\cos(t),s\sin(t),s^2$ | 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)$ | 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)$ | 104148 | halt | 19496.602 | 714.161 | 43018 | 21 | N(R) | 186 | implicit | |
| 6. | sphere2 | $\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)$ | 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)$ | 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))$ | >1812221 | not computed | not computed | not computed | not computed | not computed | not computed | implicit |
Remarks
- ↑ 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]
- ↑ Many thanks to Tatjana Kalinka for providing this list of curves and surfaces.
- ↑ 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.
- ↑ 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.
