Competing output-sensitive frame algorithms

Two output-sensitive procedures for identifying the extreme points (the “frame”) of the convex hull of a finite point set have appeared in the literature: one by Dulá and Helgason (1996) [10] and the other by Ottmann et al. (2001) [27]. The two procedures are in dual spaces and differ enough to motivate the question as to how they compare in a fair competition. We derive an improved dualized version of the procedure in Ottmann et al. (2001) [27] and compare it to the one in Dulá and Helgason (1996) [10] using a well-structured, large-scale, problem suite.