Implicitization

From ErgaWiki

(Difference between revisions)
Jump to: navigation, search
(Implicitization experiments on curves and surfaces)
Line 21: Line 21:
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>.
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>.
-
 
-
==References==
 
-
<references />
 
== Support prediction ==
== Support prediction ==
Line 29: Line 26:
{| class="experiments sortable"  
{| class="experiments sortable"  
!  No
!  No
-
! class="unsortable" | curve <ref> Many thanks to Tatjana Kalinka for providing this list of curves and surfaces. </ref>
+
! class="unsortable" | curve  
! class="unsortable" | parametric 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]. 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>
+
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]. 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) <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>
Line 761: Line 758:
|}
|}
-
== Remarks ==
+
==References==
-
 
+
<references />
-
[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/Impl2011.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.
+

Revision as of 12:16, 2 March 2012

Contents

Implicitization experiments on curves and surfaces

Implicitization is the change of parametric representation 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 circle below is given parametrically by x=cos(t), y=sin(t); its implicit equation is x^2+y^2=1.

For the case of curves, there are two equations in one parameter t. For the case of surfaces, there are 3 expressions in two parameters t,s. Additionally, in certain parameterizations, we consider families of curves/surfaces with respect to free constants a,b,c.

Each parametric expression can be transformed to a polynomial. We consider the system of polynomials in the parameters and define its sparse resultant. We compute the resultant's Newton polytope, which gives information on the implicit equation's support. Then, we compute the implicit equation by interpolation, which amounts to linear algebra.


These are some experimental results of the algorithms that compute the Newton polytope of the Sparse Resultant. For more information see [1]. 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. In our experiments we use two support prediction methods: one applies only for curves, and another is general. We present our implementation of the "curves only" method and some examples. Here we apply numeric as well as exact methods for linear solving in order to obtain coefficients of the implicit equation.

Another Maple implementation contains two implicitization methods for general support prediction that use exact solving. Examples of running these methods on the curves and surfaces.

For more information see [2].


Support prediction

Curves

No curve 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

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

Implicitization

These results have been 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

References

  1. 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) [1]
  2. I. Z. Emiris, T. Kalinka, Ch. Konaxis, Implicitization of curves and surfaces using predicted support, 2011 [2]
  3. 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.
  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.
Personal tools