A two-dimensional improvement for Farr-Gao algorithm (Q1691951)

In this paper, the author addresses the inverse problem of multivariate polynomial root-finding. More precisely, given a field \(K\) and a finite subset \(E\subset K^n\), the goal is to find a minimal generating set for the set of all polynomials in \(K[x_1,\ldots ,x_n]\) that vanish on \(E\). Indeed, the ideal generated by these polynomials is called the \textit{vanishing ideal} of \(E\). In 1982, Buchberger and Möller presented the first algorithm (based linear algebra techniques) to compute a Gröbner basis for the vanishing ideal of \(E\). Later on, \textit{J. B. Farr} and \textit{S. Gao} [Lect. Notes Comput. Sci. 3857, 118--127 (2006; Zbl 1125.13012)] (by using an incremental structure) proposed a natural generalization of Newton's interpolation for uni-variate polynomials to compute such a Gröbner basis. In the paper under review, the author considers the special case \(n=2\) and describes an improvement of the Farr-Gao algorithm by using the concept of tower subsets of a given set of points to compute a Gröbner basis for the vanishing ideal of \(E\). Experimental results illustrated in the paper show that the new algorithm is slightly more efficient than the classical one.