Computing convex quadrangulations

T. Schiffer, F. Aurenhammer, and M. Demuth


We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set.

Reference: T. Schiffer, F. Aurenhammer, and M. Demuth. Computing convex quadrangulations. Discrete Applied Mathematics, 160:648-656, 2012.