Convex Quadrangulations of Bichromatic Point Sets
Alexander Pilz, Carlos Seara · International Journal of Computational Geometry & Applications · 2019
We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set [Formula: see text] of points with each point either red or blue, does there exist a convex quadrangulation of [Formula: see text] in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets.