Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains
We study some fundamental computational geometry problems with the goal to exploit structure in input data that is given as a sequence C = (p(1), p(2), . . . ,p(n)) of points that are "almost sorted" in the sense that the polygonal chain they define has a possibly small number, k, of self-intersections, or the chain can be partitioned into a small number, X, of simple subchains. We give results th