×

Computing the Newton polygon of the implicit equation. (English) Zbl 1205.14040

Summary: We consider rationally parameterized plane curves, where the polynomials in the parameterization have fixed supports and generic coefficients. We apply sparse (or toric) elimination theory in order to determine the vertex representation of the implicit equation’s Newton polygon. In particular, we consider mixed subdivisions of the input Newton polygons and regular triangulations of point sets defined by Cayley’s trick. We consider polynomial and rational parameterizations, where the latter may have the same or different denominators; the implicit polygon is shown to have, respectively, up to four, five, or six vertices.

MSC:

14H50 Plane and space curves
14M25 Toric varieties, Newton polyhedra, Okounkov bodies
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)

Software:

TrIm
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Corless, R.M., Giesbrecht, M.W., Kotsireas, I.S., Watt, S.M.: Numerical implicitization of parametric hypersurfaces with linear algebra. In: Artificial Intelligence & symbolic Computation, (Madrid, 2000), pp. 174–183. Springer, Berlin (2001) · Zbl 1042.65020
[2] Cox D.A., Sederberg T.W., Chen F.: The moving line ideal basis of planar rational curves. Comput. Aided Geom. Des. 15(8), 803–827 (1998) · Zbl 0908.68174
[3] Dickenstein A., Feichtner E.M., Sturmfels B.: Tropical discriminants. J. Am. Math. Soc. 20(4), 1111–1133 (2007) · Zbl 1166.14033
[4] Dokken, T.: Approximate implicitization. In: Mathematical Methods for Curves and Surfaces (Oslo, 2000), pp. 81–102. Vanderbilt University, Nashville (2001) · Zbl 0989.65019
[5] D’Andrea C., Sombra M.: The Newton polygon of a rational plane curve. In: Gonzalez-Vega, L., Lazard, S. (eds) Math. in Comp. Science (this Issue), Birkhäuser, Basel (2010) · Zbl 1205.14039
[6] D’Andrea C., Sombra M.: Rational parametrizations, intersection theory and Newton polytopes. In: Emiris, I.Z., Sottile, F., Theobald, T. (eds) Nonlinear Computational Geometry. IMA Volumes in Math. & Appl., vol. 151, pp. 35–50. Springer, New York (2009) · Zbl 1181.14063
[7] Emiris, I.Z., Fisikopoulos, V., Konaxis, C.: Regular triangulations and resultant polytopes. 26th Europ. Workshop Comput. Geometry, Dortmund, Germany (2010) · Zbl 1293.68288
[8] Emiris, I.Z., Kotsireas, I.S.: Implicitization with polynomial support optimized for sparseness. In: Proc. Intern. Conf. Comput. Science & Appl. 2003, Montreal (Intern. Workshop Comp. Graphics & Geom. Modeling). LNCS, vol. 2669, pp. 397–406. Springer, Berlin (2003)
[9] Emiris, I.Z., Kotsireas, I.S.: Implicitization exploiting sparseness. In: Janardan, R., Smid, M., Dutta, D. (eds.) Geometric & Algorithmic Aspects of Comp.-Aided Design & Manufacturing. DIMACS, vol. 67, pp. 281–298. DIMACS (2005) · Zbl 1272.65018
[10] Emiris, I.Z., Konaxis, C., Palios, L.: Computing the Newton polytope of specialized resultants. MEGA 2007, RICAM (Johann Radon Institute for Computational and Applied Mathematics), Strobl, Austria · Zbl 1205.14040
[11] Esterov, A., Khovanskii, A.: Elimination theory and Newton polytopes (2007). arXiv.org:math/0611107v2 · Zbl 1192.14038
[12] Gelfand I.M., Kapranov M.M., Zelevinsky A.V.: Newton polytopes of the classical resultant and discriminant. Adv. Math. 84, 237–254 (1990) · Zbl 0721.33002
[13] Gelfand I., Kapranov M., Zelevinsky A.: Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston (1994) · Zbl 0827.14036
[14] Michiels T., Verschelde J.: Enumerating regular mixed-cell configurations. Discret. Comp. Geom. 21(4), 569–579 (1999) · Zbl 0951.52012
[15] Philippon, P., Sombra, M.: A refinement of the Kusnirenko–Bernstein estimate. Tech. Report (2007). arXiv.org:0709.3306
[16] Santos, F.: The Cayley trick and triangulations of products of simplices. In: Integer Points in Polyhedra: Geometry, Number Theory, Algebra, Optimization. Contemporary Mathematics, vol. 374, pp. 151–177. AMS, Philadelphia (2005) · Zbl 1079.52508
[17] Sederberg T.W.: Improperly parametrized rational curves. Comput. Aided Geom. Des. 3(1), 67–75 (1986) · Zbl 0594.65006
[18] Sendra, J.R., Winkler, F.: Computation of the degree of rational maps between curves. In: Proc. Intern. Symp. Symbolic & Algebraic Computation, pp. 317–322. ACM Press, New York (2001) · Zbl 1356.14054
[19] Sturmfels B.: On the Newton polytope of the resultant. J. Algebraic Comb. 3(2), 207–236 (1994) · Zbl 0798.05074
[20] Sturmfels, B., Tevelev, J., Yu, J.: The Newton polytope of the implicit equation. Moscow Math. J. 7(2) (2007) · Zbl 1133.13026
[21] Sturmfels B., Yu J.T.: Minimal polynomials and sparse resultants. In: Orecchia, F., Chiantini, L. (eds) Zero-Dimensional Schemes Proc Ravello, June 1992, pp. 317–324. De Gruyter, Berlin (1994) · Zbl 0828.12008
[22] Sturmfels B., Yu J.: Tropical implicitization and mixed fiber polytopes. In: Stillman, M., Verschelde, J., Takayama, N. (eds) Software for Algebraic Geometry. IMA Volumes in Math. & its Appl., vol 148, pp. 111–131. Springer, New York (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.