Implicitization of curves and (hyper)surfaces using predicted support

Emiris, Ioannis and Kalinka, Tatjana and Konaxis, Christos and Luu Ba, Thang (2012) Implicitization of curves and (hyper)surfaces using predicted support. Theoretical Computer Science - Special Issue on Symbolic and Numeric Computation, 2012. (In Press)

This is the latest version of this item.

[img] Text
acmac-0194.pdf

Download (640Kb)

Abstract

We reduce implicitization of rational planar parametric curves and (hyper)surfaces to linear algebra, by interpolating the coefficients of the implicit equation. For predicting the implicit support, we focus on methods that exploit input and output structure in the sense of sparse (or toric) elimination theory, namely by computing the Newton polytope of the implicit polynomial, via sparse resultant theory. Our algorithm works even in the presence of base points but, in this case, the implicit equation shall be obtained as a factor of the produced polynomial. We implement our methods on Maple, and some on Matlab as well, and study their numerical stability and efficiency on several classes of curves and surfaces. We apply our approach to approximate implicitization, and quantify the accuracy of the approximate output, which turns out to be satisfactory on all tested examples; we also relate our measures to Hausdorff distance. In building a square or rectangular matrix, an important issue is (over)sampling the given curve or surface: we conclude that unitary complexes offer the best tradeoff between speed and accuracy when numerical methods are employed, namely SVD, whereas for exact kernel computation random integers is the method of choice. We compare our prototype to existing software and find that it is rather competitive.

Item Type: Article
Subjects: Q Science > QA Mathematics
Depositing User: Christos Konaxis
Date Deposited: 19 Mar 2013 12:14
Last Modified: 19 Sep 2017 18:08
URI: http://preprints.acmac.uoc.gr/id/eprint/194

Available Versions of this Item

Actions (login required)

View Item View Item