Complexity of Approximation by Conic Splines (Extended Abstract)

Sylvain Petitjean, Sunayana Ghosh, Gert Vegter

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

78 Downloads (Pure)


In this paper we show that the complexity, i.e., the number of elements, of a parabolic or conic spline approximating a sufficiently smooth curve with non-vanishing curvature to within Hausdorff distance ε is c1ε^−1/4 + O(1), or c2ε^−1/5 + O(1), respectively. The constants c1 and c2 are expressed in the Euclidean and affine curvature of the curve. We also prove that the Hausdorff distance between a curve and an optimal conic arc tangent at its endpoints is increasing with its arc-length, provided the affine curvature along the arc is monotone. We use this property in a simple bisection algorithm for computing an optimal parabolic or conic spline.
Original languageEnglish
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages4
Publication statusPublished - 2007

Cite this