research-article

Implicitization of curves and surfaces using predicted support

Authors:

Ioannis Z. Emiris,

Tatjana Kalinka,

Christos KonaxisAuthors Info & Claims

SNC '11: Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation

Pages 137 - 146

https://doi.org/10.1145/2331684.2331705

Published: 07 June 2012 Publication History

Abstract

We reduce implicitization of rational parametric curves and (hyper)surfaces to linear algebra, by interpolating the coefficients of the implicit equation. For this, we may use any method for predicting the implicit support. We focus on methods that exploit input structure in the sense of sparse (or toric) elimination theory, namely by computing the Newton polytope of the implicit polynomial. We offer a public-domain implementation of our methods, and study their numerical stability and efficiency on several classes of plane curves and surfaces, and discuss how it can be used for approximate implicitization in the setting of sparse elimination.

References

[1]

M. Aigner, A. Poteaux, B. Juttler. Approximate implicitization of space curves. Symbolic & Numer. Comp, Springer, 2011. To appear

[2]

R. Corless, M. Giesbrecht, I. S. Kotsireas, and S. Watt. Numerical implicitization of parametric hypersurfaces with linear algebra. In Proc. AISC, pp. 174--183, 2000.

Digital Library

[3]

D. A. Cox, J. B. Little, and D. O'Shea. Using Algebraic Geometry, vol. 185 of GTM. Springer, 1998.

[4]

M. Cueto, E. Tobis, and J. Yu. An implicitization challenge for binary factor analysis. J. Symbolic Computation, 45(12):1296--1315, 2010.

Digital Library

[5]

M. A. Cueto. Tropical Implicitization. PhD thesis, Dept Mathematics, UC Berkeley, 2010.

[6]

C. D'Andrea and M. Sombra. The Newton polygon of a rational plane curve. Math. in Computer Science, 4(1):3--24, 2010.

[7]

A. Dickenstein, E. M. Feichtner, and B. Sturmfels. Tropical discriminants. J. AMS, 1111--1133, 2007.

[8]

T. Dokken and J. B. Thomassen. Overview of approximate implicitization. Topics in algebraic geometry and geometric modeling, 334:169--184, 2003.

[9]

I. Z. Emiris, V. Fisikopoulos, and C. Konaxis. Regular triangularions and resultant polytopes. In Proc. Europ. Workshop Comp. Geometry, pp. 137--140, 2010.

[10]

I. Z. Emiris, C. Konaxis, and L. Palios. Computing the Newton polygon of the implicit equation. Tech. Report 0811.0103v1, arXiv, 2007.

[11]

I. Z. Emiris, C. Konaxis, and L. Palios. Computing the Newton polygon of the implicit equation. Math. in Computer Science, Special Issue, 4(1):25--44, 2010.

[12]

I. Z. Emiris and I. S. Kotsireas. Implicit polynomial support optimized for sparseness. In Proc. Conf. Comput. science Appl., pp. 397--406, Springer, 2003

Digital Library

[13]

A. Esterov and A. Khovanski. Elimination theory and Newton polytopes. ArXiv Math., Nov. 2006.

[14]

L. Gonzalez-Vega. Implicitization of parametric curves and surfaces by using multidimensional Newton formulae. J. Symbolic Comput., 23(2-3):137--151, 1997.

Digital Library

[15]

R. Krasauskas. Personal communication, 2011.

[16]

I. S. Kotsireas and E. Lau. Implicitization of polynomial curves. In Proc. ASCM, pp. 217--226, Beijing, 2003.

[17]

A. Marco and J. Martinez. Implicitization of rational surfaces by means of polynomial interpolation. CAGD, 19:327--344, 2002.

Digital Library

[18]

J. Rambau. TOPCOM: Triangulations of point configurations and oriented matroids. Intern. Conf. Math. Software, pp. 330--340. World Scientific, 2002.

[19]

M. Shalaby and B. Jüttler. Approximate implicitization of space curves and of surfaces of revolution. Algebraic Geometry & Geom. Modeling, pp. 215--228. Springer, 2008.

[20]

B. Sturmfels. On the Newton polytope of the resultant. J. Algebraic Combin., 3:207--236, 1994.

Digital Library

[21]

B. Sturmfels, J. Tevelev, and J. Yu. The Newton polytope of the implicit equation. Moscow Math. J., 7(2), 2007.

[22]

B. Sturmfels and J. Yu. Tropical implicitization and mixed fiber polytopes. In Soft. for Algebraic Geom, vol. 148 of IMA pp. 111--131, Springer, 2008.

[23]

B. Sturmfels and J. T. Yu. Minimal polynomials and sparse resultants. In Proc. Zero-dimensional schemes (Ravello, 1992), pp. 317--324. De Gruyter, 1994.

[24]

E. Wurm, J. Thomassen, B. Juttler, T. Dokken. Comparative benchmarking of methods for approximate implicitization. In Geom. Modeling & computing 2003, pp. 537--548. 2004

[25]

R. Zippel. Effective Polynomial Computation. Kluwer Academic Publishers, Boston, 1993.

Cited By

Emiris IKalinka TKonaxis CBa T(2013)Implicitization of curves and (hyper)surfaces using predicted supportTheoretical Computer Science10.1016/j.tcs.2012.10.018479(81-98)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.10.018
Rueda S(2013)Linear sparse differential resultant formulasLinear Algebra and its Applications10.1016/j.laa.2013.01.016438:11(4296-4321)Online publication date: Jun-2013
https://doi.org/10.1016/j.laa.2013.01.016
Emiris IKalinka TKonaxis CLuu Ba T(2013)Sparse implicitization by interpolationComputer-Aided Design10.1016/j.cad.2012.10.00845:2(252-261)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.cad.2012.10.008
Show More Cited By

Index Terms

Implicitization of curves and surfaces using predicted support

Recommendations

A note on implicitization and normal parametrization of rational curves
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

In this paper we present a method to compute an implicitization of a rational parametrized curve in an affine space over an algebraically closed field. This method is the natural generalization of the resultant method for planar curves. For this purpose ...
Implicitization of rational ruled surfaces with µ-bases

Chen, Sederberg, and Zheng introduced the notion of a ¼-basis for a rational ruled surface in Chen et al. [Chen, F., Zheng, J., Sederberg, T. W., 2001. The μ-basis of a rational ruled surface. Comput. Aided Geom. Design 18 (1), 6172] and showed that its ...
Implicitization and parametrization of quadratic and cubic surfaces by μ-bases
Special issue on Geometric Modeling (Dagstuhl 2005)

Parametric and implicit forms are two common representations of geometric objects. It is important to be able to pass back and forth between the two representations, two processes called parameterization and implicitization, respectively. In this paper, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SNC '11: Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation

June 2012

194 pages

ISBN:9781450305150

DOI:10.1145/2331684

General Chair:
Ilias Kotsireas
Wilfrid Laurier University, Canada

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

ISSAC '11

Sponsor:

SIGSAM

ISSAC '11: International Symposium on Symbolic and Algebraic Computation

June 7, 2011 - June 9, 2012

California, San Jose

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
62
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Emiris IKalinka TKonaxis CBa T(2013)Implicitization of curves and (hyper)surfaces using predicted supportTheoretical Computer Science10.1016/j.tcs.2012.10.018479(81-98)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.10.018
Rueda S(2013)Linear sparse differential resultant formulasLinear Algebra and its Applications10.1016/j.laa.2013.01.016438:11(4296-4321)Online publication date: Jun-2013
https://doi.org/10.1016/j.laa.2013.01.016
Emiris IKalinka TKonaxis CLuu Ba T(2013)Sparse implicitization by interpolationComputer-Aided Design10.1016/j.cad.2012.10.00845:2(252-261)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.cad.2012.10.008
Emiris IFisikopoulos VKonaxis CPeñaranda LDey TWhitesides S(2012)An output-sensitive algorithm for computing projections of resultant polytopesProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261276(179-188)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261276

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten