Experimental results on quadrangulations of sets of fixed points

Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki

Research output: Contribution to journalArticlepeer-review


We consider the problem of obtaining "nice" quadrangulations of planar sets of points. For many applications "nice" means that the quadrilaterals obtained are convex if possible and as "fat" or squarish as possible. For a given set of points a quadrangulation, if it exists, may not admit all its quadrilaterals to be convex. In such cases we desire that the quadrangulations have as many convex quadrangles as possible. Solving this problem optimally is not practical. Therefore we propose and experimentally investigate a heuristic approach to solve this problem by converting "nice" triangulations to the desired quadrangulations with the aid of maximum matchings computed on the dual graph of the triangulations. We report experiments on several versions of this approach and provide theoretical justification for the good results obtained with one of these methods. The results of our experiments are particularly relevant for those applications in scattered data interpolation which require quadrangulations that should stay faithful to the original data.

Original languageEnglish (US)
Pages (from-to)533-552
Number of pages20
JournalComputer Aided Geometric Design
Issue number7
StatePublished - Jul 2002


  • Matchings
  • Mesh generation
  • Quadrangulations
  • Triangulations

ASJC Scopus subject areas

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Experimental results on quadrangulations of sets of fixed points'. Together they form a unique fingerprint.

Cite this