Converting triangulations to quadrangulations

Suneeta Ramaswamia, Pedro Ramos, Godfried Toussaint

Research output: Contribution to journalArticle

Abstract

We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most [n/3], and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most [n/4] Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.

Original languageEnglish (US)
Pages (from-to)257-276
Number of pages20
JournalComputational Geometry: Theory and Applications
Volume9
Issue number4
DOIs
StatePublished - Mar 1998

Keywords

  • Finite element methods
  • Matchings
  • Mesh-generation
  • Quadrangulations
  • Scattered data interpolation
  • Simple polygons
  • Triangulations

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Converting triangulations to quadrangulations'. Together they form a unique fingerprint.

  • Cite this