Quadrangulations on 3-Colored Point Sets with Steiner Points and Their Winding Numbers

摘要: Let P be a point set on the plane, and consider whether is quadrangulatable, that is, there exists 2-connected plane graph G with each edge straight segment such V(G) = P, outer cycle of coincides convex hull Conv(P) finite face quadrilateral. It easy to see it possible if only an even number points lie Conv(P). Hence we give k-coloring same problem, avoiding edges joining two vertices color. In this case, always assume lying any consecutive have distinct colors. However, for every k ? 2, k-colored non-quadrangulatable P. So introduce Steiner points, which can put in position interior may colored by When Alvarez et al. proved consists $${\frac{n}{2}}$$ n 2 red blue general position, then adding Q $${|Q| \leq \lfloor \frac{n-2}{6} \rfloor + \frac{n}{4} +1}$$ | ≤ - 6 4 1 , but 3-colored no matter how many are added. paper, define winding prove added quadrangulatable zero. \frac{7n+34m-48}{18}}$$ 7 34 m 48 18 where |P| 2m.