The Vanishing Ideal Of A Finite Set Of Points With Multiplicity Structures

The study of the vanishing ideal of a finite set of points has an important theoreticalvalue in the polynomial system solving problem and the interpolation problem, and can beapplied to many fields, including biology, statistics and coding theory.Given a finite set of arbitrarily distributed points in afne space with multiplicity struc-tures, we present an algorithm to compute the reduced Gro¨bner basis of the vanishing idealunder the lexicographic order. We split the problem into several smaller ones which can besolved by induction over variables and then use our new algorithm for intersection of idealsto compute the result of the original problem. The new algorithm for intersection of idealsis mainly based on the Extended Euclidean Algorithm. Our method discloses the essentialgeometric connection between the relative position of the points with multiplicity structuresand the leading monomials of the reduced Gro¨bner basis of the vanishing ideal.