Experimental Analysis of a Kinetic Convex Hull Algorithm

Given n points continuously moving in 2d space, we want to maintain their convex hull eachtime. In this paper, first we use the kinetic data structure (KDS) framework and define a new KDSnamed Spiral. After that, we turn to both theoretical and experimental evaluations of our KDS; intheoretical evaluation, consider the four quality measures of kinetic data structures in the worstcase. but in the experimental evaluation results of a simulation program are used to estimate theaverage case. We suggest an alternative efficiency parameter instead of previously defined anddefine a new responsiveness measure for the average case. The experimental factors are muehbetter than the theoretical worst case (this is especially true for the efficiency parameter; logʹninstead of n.); hence conclude that we canʹt reject a KDS with rather large theoretical worst caseparameters. However, this study shows that when working with random positions, the worst casesused to evaluate a KDS arenʹt alway, sufficient because these are rarely occurred and the expectedaverage is so mueh better. In the worst case, from point of view of responsiveness, efficiency,locality and compactness our KDS belongs to O(n), O(n), O(C) and O(n) respectively (C is aconstant number) and in the average case, these parameters for our KDS are O(log n),O(log^2n), O(C)and O(n) respectively. Note that previously, the two last parameters was O (log n) and O (n log n).