How good is the Chord algorithm?
Constantinos Daskalakis,
Ilias Diakonikolas and Mihalis Yannakakis
21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010
Abstract:
The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the chord algorithm, as compared with the optimal approximation that achieves a desired accuracy with the minimum number of points, and prove sharp upper and lower bounds, both in the worst case and average case setting.
Full version: to be posted