Fitting curves and surfaces with constrained implicit polynomials

A problem which often arises while fitting implicit polynomials to 2D and 3 D data sets is the following: Although the data set is simple, the fit exhi bits undesired phenomena, such as loops, holes, extraneous components, etc. Previous work tackled these problems by optimizing heuristic cost function s, which penalize some of these topological problems in the fit. This paper suggests a different approach-to design parameterized families of polynomi als whose zero-sets are guaranteed to satisfy certain topological propertie s. Namely, we construct families of polynomials with star-shaped zero-sets, as well as polynomials whose zero-sets are guaranteed not to intersect an ellipse circumscribing the data or to be entirely contained in such an elli pse. This is more rigorous than using heuristics which may fail and result in pathological zero-sets. The ability to parameterize these families depen ds heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful recent results from real algebraic geometry.