2
$\begingroup$

Problem

Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the linearly interpolated values of the query points according to the data. We assume $q_i \in (\min_j x_j, \max_j x_j)$

I heard off-hand that this problem could be solved in $O(m+n)$ time but can only think of an $O(m \log n)$ algorithm. I can't seem to find this particular problem in any of the algorithm textbooks.

Linearithmic Algorithm

interpolated = []
for q in qs:
    find x[i] such that x[i] <= q <= x[i+1] with binary search
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

This gives us a runtime of $O(m \log n)$, it's unclear to me how to get this down to $O(m + n)$ as the search for $x_i$ must be done for every query point.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are query points sorted? $\endgroup$
    – Vladislav Bezhentsev
    May 31, 2020 at 14:01
  • $\begingroup$ Let's assume yes. I see where you're going now, you go through the sorted data points and the query points at the same time meaning you only have to do a full search once. The rest of the query points are handled by traversal. Is that right? $\endgroup$
    – James Cagalawan
    May 31, 2020 at 14:14
  • $\begingroup$ I'm not sure, what do you mean by " The rest of the query points are handled by traversal." But yes, the idea is to iterate through data and query points simultaneously using two pointers. This is the same idea which is used in the merge step of merge sort algorithm. $\endgroup$
    – Vladislav Bezhentsev
    May 31, 2020 at 14:31
  • $\begingroup$ Yeah, that's what I meant. $\endgroup$
    – James Cagalawan
    May 31, 2020 at 14:38
  • $\begingroup$ I've edited the question to add the sorted assumption on the query points, thanks Vladislav. $\endgroup$
    – James Cagalawan
    May 31, 2020 at 15:18

1 Answer 1

Reset to default
0
$\begingroup$

You only need to perform binary search for the first element and then iterate simultaneously through the data points and query points.

Pseudocode

interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search

for q in qs:
    while not x[i] <= q <= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.