Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets

Results

From running the two algorithms on many sets of points, it can be observed that:

The SRC algorithm produces about 20% more convex quadrangles than the other two algorithms
The maximum angle is about 45 degrees larger than that produced by the SI algorithm
The minimum angle is about 11 degrees larger than that produced by the SI algorithm

See the accompanying article for a thorough description of the testing methodology.

Figure 1: Arkin's algorithm on 50 points

Figure 2: Sequential insertion algorithm on 50 points

Figure 3: Bose/Toussaint algorithm on 50 points

Figure 4: Arkin's algorithm on 500 points

Figure 5: Sequential insertion algorithm on 500 points

Figure 6: Bose/Toussaint algorithm on 500 points