Computing convex quadrangulations

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

Abstract:

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: F. Aurenhammer, M. Demuth, and T. Schiffer. Computing convex quadrangulations. In Proc. 5th Ann. Int. Symp. Voronoi Diagrams in Science and Engineering, Voronoi's Impact on Modern Science, volume 4, pages 32-43, Kiev, Ukraine, 2008.