Minkowski Decomposition and Geometric Predicates in Sparse Implicitization
Abstract
Based on the computation of a polytope Q, called the predicted polytope, containing the Newton polytope P of the implicit equation, implicitization of a parametric hypersurface is reduced to computing the nullspace of a numeric matrix. Polytope Q may contain P as a Minkowski summand, thus jeopardizing the efficiency of sparse implicitization. Our contribution is twofold. On one hand we tackle the aforementioned issue in the case of 2D curves and 3D surfaces by Minkowski decomposing Q, thus detecting the Minkowski summand relevant to implicitization: we design and implement in Sage a new, public domain, practical, potentially generalizable and worst-case optimal algorithm for Minkowski decomposition in 3D based on integer linear programming. On the other hand, we formulate basic geometric predicates, namely membership and sidedness for given query points, as rank computations on the interpolation matrix, thus avoiding to expand the implicit polynomial. This approach is implemented in Maple.
References
[1]
L. Busé. Implicit matrix representations of rational Bézier curves and surfaces. J. CAD, 46:14--24, 2014.
[2]
L. Busé and T. Luu Ba. The surface/surface intersection problem by means of matrix based representations. J. CAGD, 29(8):579--598, 2012.
[3]
C. D'Andrea and M. Sombra. Rational parametrizations, intersection theory and Newton polytopes. In Nonlinear Comp. Geom., volume 151 of Volumes in Math. & Appl., pages 35--50. IMA, 2009.
[4]
I. Emiris, T. Kalinka, C. Konaxis, and T. Luu Ba. Implicitization of curves and surfaces using predicted support. Theor. Comp. Science, 479:81--98, 2013.
[5]
I. Emiris, T. Kalinka, C. Konaxis, and T. Luu Ba. Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants. J. CAD, 45(2):252--261, 2013.
[6]
I. Z. Emiris, V. Fisikopoulos, C. Konaxis, and L. Peñaranda. An oracle-based, output-sensitive algorithm for projections of resultant polytopes. Int. J. Comp. Geom. App., Special Issue, 23:397--423, 2013.
[7]
I. Z. Emiris and E. P. Tsigaridas. Minkowski decomposition of convex lattice polygons. In M. Elkadi, B. Mourrain, and R. Piene, eds., Algebraic geometry and geometric modeling. Springer, 2005.
[8]
S. Gao and A. Lauder. Decomposition of polytopes and polynomials. Disc. Comp. Geom, 26:89--104, 2001.
[9]
D. Kesh and S. K. Mehta. Polynomial irreducibility testing through minkowski summand computation. In Proc. Canadian Conf. Comp. Geom., 2008.
[10]
A. Marco and J. Martinez. Implicitization of rational surfaces by means of polynomial interpolation. J. CAGD, 19:327--344, 2002.
[11]
J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701--717, 1980.
[12]
Z. Smilansky. Decomposability of polytopes and polyhedra. Geometriae Dedicata, 24(1):29--49, 1987.
[13]
B. Sturmfels, J. Tevelev, and J. Yu. The Newton polytope of the implicit equation. Moscow Math. J., 7(2), 2007.
[14]
B. Sturmfels and J. Yu. Tropical implicitization and mixed fiber polytopes. In Software for Algebraic Geometry, volume 148 of IMA Volumes in Math. & its Applic., pages 111--131. Springer, New York, 2008.
Index Terms
- Minkowski Decomposition and Geometric Predicates in Sparse Implicitization
Recommendations
Geometric operations using sparse interpolation matrices
The method applies to curves and (hyper) surfaces that may contain base point.We exploit sparseness of the parameterization and of the implicit equation.The interpolation matrix suffices for membership and sidedness predicates.Our Maple code implements ...
Minkowski Decomposition of Associahedra and Related Combinatorics
Realisations of associahedra with linear non-isomorphic normal fans can be obtained by alteration of the right-hand sides of the facet-defining inequalities from a classical permutahedron. These polytopes can be expressed as Minkowski sums and ...
Bernstein-Bezoutian matrices and curve implicitization
A new application of Bernstein-Bezoutian matrices, a type of resultant matrices constructed when the polynomials are given in the Bernstein basis, is presented. In particular, the approach to curve implicitization through Sylvester and Bezout resultant ...
Comments
Information & Contributors
Information
Published In
June 2015
374 pages
ISBN:9781450334358
DOI:10.1145/2755996
- Conference Chair:
- Daniel Robertz,
- General Chair:
- Steve Linton,
- Program Chair:
- Kazuhiro Yokoyama
Copyright © 2015 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 June 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Social Fund
- National Strategic Reference Framework (NSRF) - Research Funding Program: THALIS -UOA
Conference
ISSAC'15
Sponsor:
ISSAC'15: International Symposium on Symbolic and Algebraic Computation
July 6 - 9, 2015
Bath, United Kingdom
Acceptance Rates
ISSAC '15 Paper Acceptance Rate 43 of 71 submissions, 61%;
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 86Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)1
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in