Quadrangulating a Polygon with a Fixed Spirality using Steiner Points

Abstract

Let P be an n-sided polygon on the plane, where n >= 4. A quadrangulation of P is a geometric plane graph obtained from P by adding edges to the interior of P so that every finite face is quadrilateral. It is easy to see that $P$ does not always admit a quadrangulation. So Ramaswami et al. introduced  "Steiner points", which are auxiliary points added to P which helps quadrangulatability of P. Those points are said to be inner and outer if they are added to the interior and the exterior of P, respectively. They proved that every P with Steiner points added admits a quadrangulation, and estimated the number of those Steiner points by n, when all Steiner points are inner, and when all Steiner points are outer. On the other hand, Hidaka et al. used the notion of "spirality of P" which measures how far P is from being convex, and considered how a polygon P of spirality k admits a quadrangulation with inner Steiner points. In this paper, we consider the quadrangulatability of a polygon of P of spirality k when all Steiner points are outer, and when both inner and outer Steiner points are allowed.