Regenerative cascade homotopies for solving polynomial systems

A key step in the numerical computation of the irreducible decomposition of a polynomial system is the computation of a witness superset of the solution set. In many problems involving a solution set of a polynomial system, the witness superset contains all the needed information. Sommese and Wampler gave the first numerical method to compute witness supersets, based on dimension-by-dimension slicing of the solution set by generic linear spaces, followed later by the cascade homotopy of Sommese and Verschelde. Recently, the authors of this article introduced a new method, regeneration, to compute solution sets of polynomial systems. Tests showed that combining regeneration with the dimension-by-dimension algorithm was significantly faster than naively combining it with the cascade homotopy. However, in this article, we combine an appropriate randomization of the polynomial system with the regeneration technique to construct a new cascade of homotopies for computing witness supersets. Computational tests give strong evidence that regenerative cascade is superior in practice to previous methods.     

Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

A witness version of the Cops and Robber game

The games considered are mixtures of Searching and Cops and Robber. The cops have partial information provided via witnesses who report “sightings” of the robber. The witnesses are able to provide information about the robber’s position but not the direction in which he is moving. The robber has perfect information. In the case when sightings occur at regular intervals, we present a recognition theorem for graphs on which a single cop suffices to guarantee a win. In a special case, this recognition theorem provides a characterization.     

Reconstruction Using Witness Complexes

We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a one-parameter family of complexes that approximate S at different scales. At a high level, our method is very similar in spirit to Chew’s surface meshing algorithm, with one notable difference though: the restricted Delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. To prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted Delaunay triangulation in 2d and in 3d. Specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.     

A weak characterisation of the Delaunay triangulation

We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional (strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented by a finite point sample.      

Witness sets of projections

Elimination is a basic algebraic operation which geometrically corresponds to projections. This article describes using the numerical algebraic geometric concept of witness sets to compute the projection of an algebraic set. The ideas described in this article apply to computing the image of an algebraic set under any linear map.