research-article

Matrix Representations by Means of Interpolation

Authors:

Ioannis Z. Emiris,

Christos Konaxis,

Ilias S. Kotsireas,

Clément LarocheAuthors Info & Claims

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

Pages 149 - 156

https://doi.org/10.1145/3087604.3087629

Published: 23 July 2017 Publication History

Abstract

We examine implicit representations of parametric or point cloud models, based on interpolation matrices, which are not sensitive to base points. We show how interpolation matrices can be used for ray shooting of a parametric ray with a surface patch, including the case of high-multiplicity intersections. Most matrix operations are executed during pre-processing since they solely depend on the surface. For a given ray, the bottleneck is equation solving. Our Maple code handles bicubic patches in < 1 sec, though numerical issues might arise. Our second contribution is to extend the method to parametric space curves and, generally, to codimension > 1, by computing the equations of (hyper)surfaces intersecting precisely at the given object. By means of Chow forms, we propose a new, practical, randomized algorithm that always produces correct output but possibly with a non-minimal number of surfaces. For space curves, we typically obtain 3 surfaces whose polynomials are of near-optimal degree; in this case, computation reduces to a Sylvester resultant. Our Maple prototype is not faster but yields fewer equations and seems more robust than Maple's implicitize.

References

[1]

C. Bajaj and I. Ihm. 1989. Hermite Interpolation of Rational Space Curves Using Real Algebraic Surfaces. In Proc. ACM Symp. on Comput. Geometry. 94--103.

Digital Library

[2]

L. Busé. 2014. Implicit matrix representations of rational Bézier curves and surfaces. J. CAD, 46, 14--24.

Digital Library

[3]

L. Busé, D. Cox, and C. D'Andrea. 2003. Implicitization of surfaces in the projective space in the presence of base points. J. Algebra & Appl. 2, 14--24.

[4]

L. Busé and T. Luu Ba. 2012. The surface/surface intersection problem by means of matrix based representations. J. CAGD, 29 (8), 579--598.

Digital Library

[5]

R.M. Corless, M. Giesbrecht, I.S. Kotsireas, and S.M. Watt. 2000. Numerical Implicitization of Parametric Hypersurfaces with Linear Algebra. In Proc. AISC, LNAI, Springer. 174--183.

Digital Library

[6]

D. Cox, J. Little, and D. O'Shea. 2005. Using Algebraic Geometry (2nd ed.). Number 185 in GTM. Springer.

[7]

J. Dalbec and B. Sturmfels. 1995. Introduction to Chow Forms. In Invariant Methods in Discrete and Computational Geometry: Proc. Curaçao Conference, 13--17 June, 1994, Neil L. White (Ed.). Springer, 37--58.

[8]

C. D'Andrea, 2002. Macaulay-style formulas for the sparse resultant. Trans. of the AMS 354, 2595--2629.

[9]

D. Diochnos, I.Z. Emiris, and E. Tsigaridas. 2009. On the complexity of real solving bivariate systems. J. Symbolic Computation 44 (7), 818--835.

Digital Library

[10]

T. Dokken. 2001. Approximate implicitization. In Mathematical methods for curves and surfaces (Oslo 2000). Vanderbilt Univ. Press, 81--102.

Digital Library

[11]

I.Z. Emiris, V. Fisikopoulos, C. Konaxis, and L. Peñaranda. 2014. An Oracle-Based, Output-Sensitive algorithm for projections of resultant polytopes. Intern. J. Comp. Geometry & Appl., 23, 397--423.

[12]

I.Z. Emiris, T. Kalinka, and C. Konaxis. 2015. Geometric operations using sparse interpolation matrices. Graphical Models 82, 99--109.

Digital Library

[13]

I.Z. Emiris, T. Kalinka, C. Konaxis, and T. Luu Ba. 2013. Sparse implicitization by interpolation: Characterizing non-exactness, and an application to computing discriminants. J. CAD 45, 252--261.

Digital Library

[14]

I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky. 1994. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston.

[15]

D. Manocha and J.F. Canny. 1992. The Implicit Representation of Rational Parametric Surfaces. J. Symbolic Computation 13, 485--510.

Digital Library

[16]

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

Digital Library

[17]

S. Rueda, J. Sendra, and J.R. Sendra. 2013. An algorithm to parametrize approxi- mately space curves. J. Symbolic Computation 56, 80--106.

[18]

T.W. Sederberg and F. Chen. 1995. Implicitization using moving curves and surfaces. In Proc. SIGGRAPH, R. Cook (Ed.). Addison Wesley, 301--308.

Digital Library

[19]

J. Shen, L. Busé, P. Alliez, and N. Dodgson. 2016. A line/trimmed NURBS surface intersection algorithm using matrix representations. Tech. Report, INRIA. https://hal.inria.fr/hal-01268109

[20]

B. Sturmfels. 2008. Algorithms in Invariant Theory. Texts and Monographs in Symbolic Computation. Springer.

Digital Library

[21]

E.P. Tsigaridas and I.Z. Emiris. 2008. On the complexity of real root isolation using continued fractions. Theoretical Computer Science 392, 1--3, 158--173

Digital Library

Cited By

Groh FEmiris IZhi LMantzaflaris A(2020)Subdivisions for macaulay formulas of sparse systemsProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403988(218-225)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3403988
Emiris IAbramov SZima EGao X(2016)Compact Formulae in Sparse EliminationProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930943(1-4)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930943

Index Terms

Matrix Representations by Means of Interpolation
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Representation of mathematical objects
      1. Representation of polynomials
    2. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Implicit representations of high-codimension varieties
Abstract
Implicitization usually focuses on plane curves and (hyper)surfaces, in other words, varieties of codimension 1. In this paper we shift the focus on space curves and, more generally, on varieties of codimension larger than 1, and ...
Highlights
- Present an algorithm based on Chow forms to implicitize high codimensional varieties.
Using µ-bases to implicitize rational surfaces with a pair of orthogonal directrices

A rational surfaceS(s,t)=(a(t)a^@?(s),a(t)b^@?(s),b(t)c^@?(s),c(t)c^@?(s)) can be generated from two orthogonal rational planar directrices: P(t)=(a(t),b(t),c(t)) in the xz-plane and P^@?(s)=(a^@?(s),b^@?(s),c^@?(s)) in the xy-plane. Moving a scaled ...
Matrix representations for toric parametrizations

In this paper we show that a surface in P^3 parametrized over a 2-dimensional toric variety T can be represented by a matrix of linear syzygies if the base points are finite in number and form locally a complete intersection. This constitutes a direct ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

July 2017

466 pages

ISBN:9781450350648

DOI:10.1145/3087604

Editor:
Michael Burr
Clemson University, USA
,
General Chair:
Chee K. Yap
New York University, USA
,
Program Chair:
Mohab Safey El Din
University Pierre et Marie Curie, France

Copyright © 2017 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]

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union's Horizon 2020

Conference

ISSAC '17

ISSAC '17: International Symposium on Symbolic and Algebraic Computation

July 23 - 28, 2017

Kaiserslautern, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
57
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Groh FEmiris IZhi LMantzaflaris A(2020)Subdivisions for macaulay formulas of sparse systemsProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403988(218-225)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3403988
Emiris IAbramov SZima EGao X(2016)Compact Formulae in Sparse EliminationProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930943(1-4)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930943

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