Simple varieties for limited precision points

Given a finite set X of points and a tolerance ε representing the maximum error on the coordinates of each point, we address the problem of computing a simple polynomial f whose zero-locus Z(f) “almost” contains the points of X. We propose a symbolic–numerical method that, starting from the knowledge of X and ε, determines a polynomial f whose degree is strictly bounded by the minimal degree of the elements of the vanishing ideal of X. Then, in Theorem 4.3, we state the sufficient conditions for proving that Z(f) lies close to each point of X by less than ε. The validity of the proposed method relies on a combination of classical results of Computer Algebra and Numerical Analysis; its effectiveness is illustrated with a number of examples.