2013/10/07 by Ajit A. Diwan, Diwan, Ajit Arvind, Subir Kumar Ghosh +3
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Digital Image Processing Techniques
paper · pdf · doi:10.48550/arxiv.1310.1726
In this paper, we consider the problem of determining in polynomial time whether a given planar point set P of n points admits 4-connected triangulation. We propose a necessary and sufficient condition for recognizing P, and present an O(n3) algorithm of constructing a 4-connected triangulation of P. Thus, our algorithm solves a longstanding open problem in computational geometry and geometric graph theory. We also provide a simple method for constructing a noncomplex triangulation of P which requires O(n2) steps. This method provides a new insight to the structure of 4-connected triangulation of point sets.