CS1050, Spring 2006, Project 7
Delaunay Triangulation
by Jacob Bolton   Email:
Submitted: March 12, 2006

Click to insert new sites
Drag to move them
Drag them out of scree to delete
Press 'f' to recenter and rescale the sites
Press 'd' to hide/show circumcenters
Press 'n' to hide/show sie numbers

Only on local machine:
Press 'w' to print the points
Press 's' to save the points
Press 'l' to load saved points
Press 'i' to save a snapshot

My algorithm examines all possible triangles from the n points, and for each possible triangle it checks to see if any of the other points are within the inscribed circle. If no other points are within, then it is a Delaunay triangle. The number of possible triangles is number of combinations of 3 different points from the set of n points, and that means there are (n - 3) other points. The worst-case complexity for this algorithm is thus:

Here are some screenshots of randomly generated sets of points being processed and timed. The timing should verify the worst-case complexity formula.

These results are summarized here:

Points	Triangles	Avg. Time	Time Change (from previous set)
10	12	0.17 ms	na
20	31	1.0 ms	5.9x
40	69	7.2 ms	7.2x
80	148	58 ms	8.1x
160	306	470 ms	8.1x

The changes in timing vs the change in number of points indicates an exponential change in time, which was predicted by the worst-case complexity. However, the O(n^4) predicted would be expected to yeild a time change of around 16x instead of around 8x. If the worst-case complexity formula is wrong, the data suggests that it would be somewhere between O(n^3) and O(n^4), but the data could also result from the test cases not being close to a worst-case scenario. The worst case scenario would occur when the possible triangles of a set of points are ALL Delaunay triangles, and this only occurs when you have a set of 3 points. As you add more points, the number of possible triangles grows factorialy whereas the number of Delaunay triangles increases at a rate related to the number of closest, triangle-forming points, which is much smaller.

Source code: P7 pv2D

Built with Processing