Matrix Representations by Means of Interpolation
ACM ISSAC 2017: 149-156
- Contact persons: Ioannis Emiris , Christos Konaxis
- Relevant research project: ARCADES
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.