Implicitization
From ErgaWiki
(→Implicitization) |
|||
(94 intermediate revisions not shown) | |||
Line 1: | Line 1: | ||
- | + | === Implicitization experiments on curves and surfaces === | |
- | == Implicitization experiments | + | 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,<br> | ||
+ | y = -s*t - s^3*t + s*t^3,<br> | ||
+ | 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,<br> | ||
+ | F_2 = y + s*t + s^3*t - s*t^3,<br> | ||
+ | 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<br> | ||
+ | 6 4 3 | 0 6 10<br> | ||
+ | [[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 [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. | ||
+ | |||
+ | 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''' | ||
+ | {|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''' | ||
{| class="experiments sortable" | {| class="experiments sortable" | ||
! No | ! No | ||
- | ! class="unsortable" | curve | + | ! class="unsortable" | curve |
- | ! class="unsortable" | equation | + | ! class="unsortable" | parametric equation |
! class="unsortable" | supports | ! class="unsortable" | supports | ||
! <nowiki># mixed subdivisions</nowiki> | ! <nowiki># mixed subdivisions</nowiki> | ||
! class="run" | | ! 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]. | + | 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" | | ! 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> | + | 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" | | ! 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> | + | 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># mixed cell configurations</nowiki> | ||
- | ! class="unsortable" | <nowiki># | + | ! class="unsortable" | <nowiki># N(R) vertices</nowiki> |
- | ! class="unsortable" | <nowiki># all terms</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. | | 1. | ||
- | + | | astroid | |
- | | | + | |a\cos(t)^3,a\sin(t)^3 |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports1.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports1.dat supports] | ||
Line 32: | Line 413: | ||
| 289 | | 289 | ||
| 35 | | 35 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_1.dat support] | ||
|- | |- | ||
| 2. | | 2. | ||
| cardioid | | cardioid | ||
- | | | + | | $a(2\cos(t)-\cos(2t)),a(2\sin(t)-\sin(2t))$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports2.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports2.dat supports] | ||
Line 45: | Line 429: | ||
| 37 | | 37 | ||
| 10 | | 10 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_2.dat support] | ||
|- | |- | ||
| 3. | | 3. | ||
| circle | | circle | ||
- | | | + | |$ \cos(t),\sin(t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports3.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports3.dat supports] | ||
Line 58: | Line 445: | ||
| 5 | | 5 | ||
| 3 | | 3 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_3.dat support] | ||
|- | |- | ||
| 4. | | 4. | ||
| conchoid | | conchoid | ||
- | | | + | | $a+\cos(t),a\tan(t)+\sin(t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports4.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports4.dat supports] | ||
Line 71: | Line 461: | ||
| 12 | | 12 | ||
| 4 | | 4 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_4.dat support] | ||
|- | |- | ||
| 5. | | 5. | ||
| ellipse | | ellipse | ||
- | | | + | | $a\cos(t),b\sin(t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports5.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports5.dat supports] | ||
Line 84: | Line 477: | ||
| 5 | | 5 | ||
| 3 | | 3 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_5.dat support] | ||
|- | |- | ||
| 6. | | 6. | ||
- | | folium of | + | | folium of Descartes |
- | | | + | | $3at/(1+t^3),3at^2/(1+t^3)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports6.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports6.dat supports] | ||
Line 97: | Line 493: | ||
| 14 | | 14 | ||
| 6 | | 6 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_6.dat support] | ||
|- | |- | ||
| 7. | | 7. | ||
| involute of a circle | | 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] | [http://ergawiki.di.uoa.gr/curves_supports/supports7.dat supports] | ||
Line 110: | Line 509: | ||
| 14 | | 14 | ||
| 6 | | 6 | ||
+ | | [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. | ||
| nephroid | | nephroid | ||
- | | | + | | $a(3\cos(t)-\cos(3t)),a(3\sin(t)-\sin(3t))$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports8.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports8.dat supports] | ||
Line 123: | Line 525: | ||
| 289 | | 289 | ||
| 35 | | 35 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_8.dat support] | ||
|- | |- | ||
| 9a. | | 9a. | ||
- | | | + | | Plateau curve |
- | | | + | | $a\sin(3t)/\sin(t),2a\sin(2t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports9a.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports9a.dat supports] | ||
Line 136: | Line 541: | ||
| 94 | | 94 | ||
| 15 | | 15 | ||
+ | | [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. | ||
| plateau curve | | plateau curve | ||
- | | | + | | $a\sin(6t)/ \sin(2t), 2a\sin(4t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports9b.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports9b.dat supports] | ||
Line 149: | Line 557: | ||
| 42168 | | 42168 | ||
| 495 | | 495 | ||
+ | | [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. | ||
| talbot's curve | | 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] | [http://ergawiki.di.uoa.gr/curves_supports/supports10.dat supports] | ||
Line 162: | Line 573: | ||
| 1944 | | 1944 | ||
| 84 | | 84 | ||
+ | | [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. | ||
| tricuspoid | | tricuspoid | ||
- | | | + | | $a(2\cos(t)+\cos(2t)),a(2\sin(t)-\sin(2t))$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports11.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports11.dat supports] | ||
Line 175: | Line 589: | ||
| 37 | | 37 | ||
| 10 | | 10 | ||
+ | | [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] | ||
+ | | [http://ergawiki.di.uoa.gr/impl_sup/impl_support_11.dat support] | ||
|- | |- | ||
| 12. | | 12. | ||
- | | witch of | + | | witch of Agnesi |
- | | | + | | $at,a/(1 + t^2)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports12.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports12.dat supports] | ||
Line 188: | Line 605: | ||
| 2 | | 2 | ||
| 2 | | 2 | ||
+ | | [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. | ||
| circle (3 systems) | | circle (3 systems) | ||
- | | | + | | $(-t^2 +1)/s, 2t/s, t^2 -s +1$ |
| | | | ||
[http://ergawiki.di.uoa.gr/curves_supports/supports13.dat supports] | [http://ergawiki.di.uoa.gr/curves_supports/supports13.dat supports] | ||
Line 201: | Line 621: | ||
| 26 | | 26 | ||
| 6 | | 6 | ||
+ | | [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. | ||
+ | | 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" | {|class="experiments sortable" | ||
! 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 218: | Line 657: | ||
TOPCOM point2triang(sec) | TOPCOM point2triang(sec) | ||
! <nowiki># mixed cell configurations</nowiki> | ! <nowiki># mixed cell configurations</nowiki> | ||
- | ! <nowiki># | + | ! class="unsortable" | <nowiki># N(R) vertices</nowiki> |
- | ! <nowiki># all terms</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> | ||
|- | |- | ||
| | | | ||
Line 225: | Line 666: | ||
| 1. | | 1. | ||
| cylinder | | cylinder | ||
- | | | + | | $\cos(t),\sin(t),s$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports1.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports1.dat supports] | ||
Line 234: | Line 675: | ||
| 5 | | 5 | ||
| 3 | | 3 | ||
+ | | [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. | ||
| cone | | cone | ||
- | | | + | | $s\cos(t),s\sin(t),s$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports2.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports2.dat supports] | ||
Line 247: | Line 690: | ||
| 98 | | 98 | ||
| 8 | | 8 | ||
+ | | [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. | ||
| paraboloid | | paraboloid | ||
- | | | + | | $s\cos(t),s\sin(t),s^2$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports3.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports3.dat supports] | ||
Line 260: | Line 705: | ||
| 98 | | 98 | ||
| 8 | | 8 | ||
+ | | [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. | ||
| surface of revolution | | surface of revolution | ||
- | | | + | | $s\cos(t),s\sin(t),\cos(s)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports4.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports4.dat supports] | ||
Line 273: | Line 720: | ||
| 98 | | 98 | ||
| 8 | | 8 | ||
+ | | [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. | ||
| sphere | | sphere | ||
- | | | + | | $\sin(t)\cos(s),\sin(t)\sin(s),\cos(t)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports5.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports5.dat supports] | ||
Line 286: | Line 735: | ||
| 43018 | | 43018 | ||
| 21 | | 21 | ||
+ | | [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. | ||
| sphere2 | | sphere2 | ||
- | | | + | | $\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports6.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports6.dat supports] | ||
Line 299: | Line 750: | ||
| 32076 | | 32076 | ||
| 95 | | 95 | ||
+ | | [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. | ||
- | | stereographic | + | | 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] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports7.dat supports] | ||
Line 312: | Line 765: | ||
| 3126 | | 3126 | ||
| 22 | | 22 | ||
+ | | [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. | ||
- | | twisted | + | | twisted sphere |
- | | | + | | $a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))$ |
| | | | ||
[http://ergawiki.di.uoa.gr/surfaces_supports/supports8.dat supports] | [http://ergawiki.di.uoa.gr/surfaces_supports/supports8.dat supports] | ||
Line 325: | Line 780: | ||
| 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] | ||
|} | |} | ||
- | + | 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. |
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 | 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 sphere | $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 sphere | $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 |
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.