Results Time

Spent the past few days collecting and arranging my first lot of results for the 2D implementations, and so far, results are mixed. My own Contraction Approximation algorithm is the fastest in all tests (considerably faster, in most cases running in at least half the time), however, my algorithm sacrifices edge crossings.

4elt Edge Crossings y: crossings count x: scalar parameter	4elt Runtime y: runtime (ms) x: scalar parameter
55grid Edge Crossings y: crossings count x: scalar parameter	55grid Runtime y: runtime (ms) x: scalar parameter

In the charts above, results are compared against a variable I have named the scalar; a parameter introduced to change the power of repulsive forces between vertices to find better graphical results. Other variables such as the size of the viewing plane (affects the size of k) have been tested.

So what do these results show? The most obvious is that edge crossings sky rocket as the scalar increases, whereas the quad tree is unaffected, suggesting the contraction tree CA uses is more sensitive than the bulky quad tree (testing different matching algorithms will check this). Although these crossings sky rocket, during the lower scalar values, the CA algorithm matches the edge crossings of QT; so its arguable that the CA is the better option in these circumstances.

Results for the graphs data, whitaker3 and 3elt also show this same pattern across all parameters tested so far. There are no uncontrolled parameters which give either algorithm a bias; both CA and QT use code as close to each others as possible, including same data structure, same matching technique, same coarsening scheme (alterations for CA of course) and same cooling schedule.

I will update again after future analysis and when I have begun the 3D tests.