Fitting curves and surfaces with constrained implicit polynomials

Daniel Keren, Craig Gotsman

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


A problem which often arises while fitting implicit polynomials to 2D and 3D data sets is the following: Although the data set is simple, the fit exhibits undesired phenomena, such as loops, holes, extraneous components, etc. Previous work tackled these problems by optimizing heuristic cost functions, which penalize some of these topological problems in the fit. This paper suggests a different approach - to design parameterized families of polynomials whose zero-sets are guaranteed to satisfy certain topological properties. 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 ellipse. This is more rigorous than using heuristics which may fail and result in pathological zero-sets. The ability to parameterize these families depends heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful recent results from real algebraic geometry.

Original languageEnglish (US)
Pages (from-to)31-41
Number of pages11
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number1
StatePublished - 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


  • Fitting
  • Free-form shapes
  • Implicit polynomials
  • Positive polynomials
  • Starshaped curves and surfaces
  • Toplogical integrity


Dive into the research topics of 'Fitting curves and surfaces with constrained implicit polynomials'. Together they form a unique fingerprint.

Cite this