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.

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.

We derive tight expressions for the maximum number of k-faces, 0≤k≤d-1, of the Minkowski sum, P1+P2+P3, of three d-dimensional convex polytopes P1, P2 and P3 in Rd, as a function of the number of vertices of the polytopes, for any d≥2. Expressing the Minkowski sum as a section of the Cayley polytope C of its summands, counting the k-faces of P1+P2+P3 reduces to counting the (k+2)-faces of C which meet the vertex sets of the three polytopes. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of r d-polytopes in Rd, where r≥d. For d≥4, the maximum values are attained when P1, P2 and P3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves.

We develop an incremental algorithm to compute the Newton polytope of the resultant, aka resultant polytope, or its projection along a given direction. The resultant is fundamental in algebraic elimination and in implicitization of parametric hypersurfaces. Our algorithm exactly computes vertex- and halfspace-representations of the desired polytope using an oracle producing resultant vertices in a given direction. It is output-sensitive as it uses one oracle call per vertex. We overcome the bottleneck of determinantal predicates by hashing, thus accelerating execution from 18 to 100 times. We implement our algorithm using the experimental CGAL package triangulation. A variant of the algorithm computes successively tighter inner and outer approximations: when these polytopes have, respectively, 90% and 105% of the true volume, runtime is reduced up to 25 times. Our method computes instances of 5-, 6- or 7-dimensional polytopes with 35K, 23K or 500 vertices, resp., within 2hr. Compared to tropical geometry software, ours is faster up to dimension 5 or 6, and competitive in higher dimensions.