Interpolation Search


We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is O(\log n) for a list of n values, making it a very efficient algorithm for searching.

One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?

Read the rest of this entry »

Cardinal Splines (Interpolation, part IV)


In the last installment of this series, we left off Hermite splines asking how we should choose the derivatives at end points so that patches line up nicely, in a visually (or any other context-specific criterion) pleasing way.

Cardinal splines solve part of this problem quite elegantly. I say part of the problem because they address only the problem of the first derivative, ensuring that the curve resulting from neighboring patches are C^0-continuous, that is, the patches line up at the same point, and are C^1-continuous, that is, the first derivatives line up as well. We can imagine splines what are (up to) C^k-continuous, that is, patches lining up, and up to the k-th derivatives lining up as well.

Read the rest of this entry »

Hermite Splines (Interpolation, part III)


In previous posts, we discussed linear and cubic interpolation. So let us continue where we left the last entry: Cubic interpolation does not guaranty that neighboring patches join with the same derivative and that may introduce unwanted artifacts.

Well, the importance of those artifacts may vary; but we seem to be rather sensitive to curves that change too abruptly, or in unexpected ways. One way to ensure that cubic patches meet gracefully is to add the constraints that the derivative should be equal on both side of a joint. Hermite splines do just that.

Read the rest of this entry »

Cubic Interpolation (Interpolation, part II)


In a previous entry, we had a look at linear interpolation and concluded that we should prefer some kind of smooth interpolation, maybe a polynomial.

However, we must use a polynomial of sufficient degree so that neighboring patches do not exhibit very different slopes on either side of known points. This pretty much rules out quadratic polynomials, because polynomials of the form ax^2+bx+c are only capable of expressing (strictly) convex (or concave) patches. A quadratic piece-wise function would look something like:

Read the rest of this entry »

Linear Interpolation (Interpolation, part I)


In a couple of different occasions I discussed the topic of interpolation, without really going into the details. Lately, I had to interpolate data and that got me interested (again) in interpolation; and I think I should share some of the things I learned.

In this first post (of a series), let us begin by the simplest interpolation of all (after constant interpolation): linear interpolation.

Read the rest of this entry »

Getting Documents Back From JPEG Scans


We’re all looking for documentation, books, and papers. Sometimes we’re lucky, we find the pristine PDF, rendered fresh from a text processor or maybe LaTeX. Sometimes we’re not so lucky, the only thing we can find is a collection of JPEG images with high compression ratios.

Scans of text are not always easy to clean up, even when they’re well done to begin with, they may be compressed with JPEG using a (too) high compression ratio, leading to conspicuous artifacts. These artifacts must be cleaned-up before printing or binding together in a PDF.

Read the rest of this entry »