Main Page

From ErgaWiki

(Difference between revisions)
Jump to: navigation, search
(Implicitization experiments on curves and surfaces)
 
(12 intermediate revisions not shown)
Line 1: Line 1:
 +
Welcome to the Wiki Pages of ΕρΓΑ Lab (Algebraic and Geometric Algorithms) at University of Athens [http://erga.di.uoa.gr (Lab webpage)]
-
== Implicitization experiments on curves and surfaces ==
+
[[File:implicitization.jpg|frameless|link=Implicitization]]
-
{| class="experiments sortable"
+
[[Implicitization | Implicitization experiments on curves and surfaces.]]
-
!  No
+
Implicitization is the problem of transforming the parametric representation of a geometric object (e.g. curve of surface) to its implicit representation. Our group is working on matrix representations of implicit varieties, by exploiting the structure of the polynomials.
-
! class="unsortable" | curve <ref> Many thanks to Tatjana Kalinka for providing this list of curves and surfaces. </ref>
+
-
! class="unsortable" | 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># extreme terms</nowiki>
+
-
! class="unsortable" | <nowiki># all terms</nowiki>
+
-
|-
+
-
|
+
-
|-
+
-
| 1.
+
-
|| astroid
+
-
||<math>a\cos(t)^3,a\sin(t)^3</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports1.dat supports]
+
-
| class="topcom" | 289
+
-
| 193.62
+
-
| 0.048
+
-
| 0.452
+
-
| 289
+
-
| 35
+
-
| 454
+
-
|-
+
-
| 2.
+
-
| cardioid
+
-
| <math>a(2\cos(t)-\cos(2t)),a(2\sin(t)-\sin(2t))</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports2.dat supports]
+
-
| class="topcom" | 37
+
-
| 6.52
+
-
| 0.005
+
-
| 0.024
+
-
| 37
+
-
| 10
+
-
| 33
+
-
|-
+
-
| 3.
+
-
| circle
+
-
|<math> \cos(t),\sin(t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports3.dat supports]
+
-
| class="topcom" | 5
+
-
| 0.004
+
-
| 0.016
+
-
| 0.004
+
-
| 5
+
-
| 3
+
-
| 4
+
-
|-
+
-
| 4.
+
-
| conchoid
+
-
| <math>a \cos(t),ah \sin(t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports4.dat supports]
+
-
| class="topcom" | 12
+
-
| 0.84
+
-
| 0.003
+
-
| 0.008
+
-
| 12
+
-
| 4
+
-
| 6
+
-
|-
+
-
| 5.
+
-
| ellipse
+
-
| <math>a\cos(t),b\sin(t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports5.dat supports]
+
-
| class="topcom" | 5
+
-
| 0.15
+
-
| 0.001
+
-
| 0.004
+
-
| 5
+
-
| 3
+
-
| 4
+
-
|-
+
-
| 6.
+
-
| folium of descartes
+
-
| <math>3ah/(1+ h^3), 3ah^2/(ah^3)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports6.dat supports]
+
-
| class="topcom" | 14
+
-
| 0.94
+
-
| 0.004
+
-
| 0.008
+
-
| 14
+
-
| 6
+
-
| 10
+
-
|-
+
-
| 7.
+
-
| involute of a circle
+
-
| <math>a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports7.dat supports]
+
-
| class="topcom" | 14
+
-
| 1.00
+
-
| 0.001
+
-
| 0.007
+
-
| 14
+
-
| 6
+
-
| 7
+
-
|-
+
-
| 8.
+
-
| nephroid
+
-
| <math>a(3\cos(t)-\cos(3t)),a(3\sin(t)-\sin(3t))</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports8.dat supports]
+
-
| class="topcom" | 289
+
-
| 195.27
+
-
| 0.004
+
-
| 0.240
+
-
| 289
+
-
| 35
+
-
| 454
+
-
|-
+
-
| 9a.
+
-
| plateau curve
+
-
| <math>a\sin(3t)/\sin(t),2a\sin(2t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports9a.dat supports]
+
-
| class="topcom" | 94
+
-
| 33.02
+
-
| 0.012
+
-
| 0.064
+
-
| 94
+
-
| 15
+
-
| 55
+
-
|-
+
-
| 9b.
+
-
| plateau curve
+
-
| <math>a\sin(6t)/ \sin(2t), 2a\sin(4t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports9b.dat supports]
+
-
| class="topcom" | 42168
+
-
| class="halt" | halt
+
-
| 25.934
+
-
| 85.597
+
-
| 42168
+
-
| 495
+
-
| class="halt" | not computed
+
-
|-
+
-
| 10.
+
-
| talbot's curve
+
-
| <math>(a^2 + f^2 \sin( t)^2) \cos( t)/a, (a^2 - 2f^2 + (f^2)\sin(t)^2)\sin(t)/b </math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports10.dat supports]
+
-
| class="topcom" | 1944
+
-
| 3948.80
+
-
| 0.416
+
-
| 2.356
+
-
| 1944
+
-
| 84
+
-
| 1600
+
-
|-
+
-
| 11.
+
-
| tricuspoid
+
-
| <math>a(2\cos(t)+\cos(2t)),a(2\sin(t)-\sin(2t))</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports11.dat supports]
+
-
| class="topcom" | 37
+
-
| 6.20
+
-
| 0.008
+
-
| 0.024
+
-
| 37
+
-
| 10
+
-
| 33
+
-
|-
+
-
| 12.
+
-
| witch of agnesi
+
-
| <math>ah,a/(1 h^2)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports12.dat supports]
+
-
| class="topcom" | 2
+
-
| 0.03
+
-
| 0.007
+
-
| 0.004
+
-
| 2
+
-
| 2
+
-
| 2
+
-
|-
+
-
| 13.
+
-
| circle (3 systems)
+
-
| <math>(-t^2 +1)/s, 2t/s, t^2 -s +1</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/curves_supports/supports13.dat supports]
+
-
| class="topcom" | 26
+
-
| 6.00
+
-
| 0.020
+
-
| 0.052
+
-
| 26
+
-
| 6
+
-
| 7
+
-
|}
+
-
 
+
(figure of the Newton polytope of a sparse resultant, used for sparse implicitization)
-
{|class="experiments sortable"
+
-
! No
+
-
! surface
+
-
! class="unsortable" | 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>
+
-
! <nowiki># extreme terms</nowiki>
+
-
! <nowiki># all terms</nowiki>
+
-
|-
+
-
|
+
-
|-
+
-
| 1.
+
-
| cylinder
+
-
| <math>\cos(t),\sin(t),s</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports1.dat supports]
+
-
| class="topcom" | 5
+
-
| 0.24
+
-
| 0.003
+
-
| 0.006
+
-
| 5
+
-
| 3
+
-
| 4
+
-
|-
+
-
| 2.
+
-
| cone
+
-
| <math>s\cos(t),s\sin(t),s</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports2.dat supports]
+
-
| class="topcom" | 122
+
-
| 73.45
+
-
| 0.192
+
-
| 0.288
+
-
| 98
+
-
| 8
+
-
| 14
+
-
|-
+
-
| 3.
+
-
| paraboloid
+
-
| <math>s\cos(t),s\sin(t),s^2</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports3.dat supports]
+
-
| class="topcom" | 122
+
-
| 71.60
+
-
| 0.192
+
-
| 0.296
+
-
| 98
+
-
| 8
+
-
| 37
+
-
|-
+
-
| 4.
+
-
| surface of revolution
+
-
| <math>s\cos(t),s\sin(t),\cos(s)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports4.dat supports]
+
-
| class="topcom" | 122
+
-
| 71.80
+
-
| 0.193
+
-
| 0.288
+
-
| 98
+
-
| 8
+
-
| 37
+
-
|-
+
-
| 5.
+
-
| sphere
+
-
| <math>\sin(t)\cos(s),\sin(t)\sin(s),\cos(t)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports5.dat supports]
+
-
| class="topcom" | 104148
+
-
| class="halt" | halt
+
-
| 19496.602
+
-
| 714.161
+
-
| 43018
+
-
| 21
+
-
| 186
+
-
|-
+
-
| 6.
+
-
| sphere2
+
-
| <math>\cos(t)\cos(s),\sin(t)\cos(s),\sin(s)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports6.dat supports]
+
-
| class="topcom" | 76280
+
-
| class="halt" | halt
+
-
| 4492.977
+
-
| 397.157
+
-
| 32076
+
-
| 95
+
-
| 776
+
-
|-
+
-
| 7.
+
-
| stereographic shpere
+
-
| <math>2t/(1 t^2 s^2),2s/(1 t^2 s^2),(t^2 s^2-1)/(1 t^2 s^2)</math>
+
-
|
+
-
[http://ergawiki.di.uoa.gr/surfaces_supports/supports7.dat supports]
+
-
| class="topcom" | 3540
+
-
| 7112.54
+
-
| 25.402
+
-
| 11.025
+
-
| 3126
+
-
| 22
+
-
| 283
+
-
|-
+
-
| 8.
+
-
| twisted shpere
+
-
| <math>a(\cos(t) t(\sin(t)),a(\sin(t)-t\cos(t))</math>
+
-
|
+
-
[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
+
-
|}
+
-
 
+
-
== Remarks ==
+
-
 
+
-
<references />
+

Current revision as of 21:29, 16 December 2015

Welcome to the Wiki Pages of ΕρΓΑ Lab (Algebraic and Geometric Algorithms) at University of Athens (Lab webpage)

Implicitization experiments on curves and surfaces. Implicitization is the problem of transforming the parametric representation of a geometric object (e.g. curve of surface) to its implicit representation. Our group is working on matrix representations of implicit varieties, by exploiting the structure of the polynomials.

(figure of the Newton polytope of a sparse resultant, used for sparse implicitization)

Personal tools