Converting triangulations to quadrangulations

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