Finding the point that maximizes a linear function

Question

Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in Q$ (a positive integer), we need to find the point that maximizes the linear function $c_j \cdot x+y$.

Ideally, I would like to preprocess all the points in at most $O(N \log N)$ time and then answer the query for each $c_j \in Q$ in $O(\log N)$ (or maybe even constant) time.

I feel there is such an algorithm where I can sort the points by $x_i$ and/or $y_i$ and do some binary searches but it is more complex than I thought. Any there tradeoffs between preprocessing vs answering time or lower bounds known for this problem?

Edit : A fellow graduate student gave the following idea - constructing a convex hull of the $N$ points, sorting the slopes of the line segments formed by consecutive points on the hull and then finding the line segments with the slope "closest" to $-c_j$ will identify the point that maximizes the linear function $c_j x + y$. I think this works but will verify the details tomorrow. My sleep will be ruined if there is a bug.

Answer 1

Another Answer:

1. Find the 2D maximal point set. Let us call it the set $M$.
2. Find the convex hull of $M$. Let us call it $co(M)$.

The preprocessing time for the two step is $O(n \log n)$.

Now, for the line: $c_i \cdot x + y = 0$, you need to find the point in $M$ that is farthest from the line. That point must lie on the boundary of $co(M)$. Note that distances of the points on the convex hull first increase and then decrease. You need to find that point on the boundary where this transition happens. It can be done in $O(\log n)$ time using binary search.

---

Explanation: Firstly note that $c_i, x_i,$ and $y_i$ are all positive numbers. Therefore, if $(x_b,y_b)$ dominates $(x_a,y_a)$, i..e, $x_b \geq x_a$ and $y_b \geq y_a$, then, it implies $c_i \cdot x_b + y_b \geq c_i \cdot x_a + y_a$. Therefore, an optimal solution must belongs to $M$.

Now, let us call the line $c_i \cdot x + y = 0$ as $\ell$. The distance of a point $(x_a,y_a)$ from $\ell$ is: $\frac{|c_i \cdot x_a + y_a|}{\sqrt{c_{i}^{2}+1} }$. Since $c_i, x_a,$ and $y_a$ are all positive numbers, and the denominator $\sqrt{c_{i}^{2}+1}$ is the same for all the points, a point maximizes the value $c_i \cdot x + y$ if and only if it farthest from line $\ell$. Therefore, we need to find the point in $M$ that is farthest from line $\ell$. The rest of the procedure is simple.

In fact, we do not even need to compute $M$. We could have directly considered the original set of points to compute the convex hull. But computing $M$ would only decrease the query time complexity.

Answer 2

Find the 2D maximal point set. Let us call it the set $M$. The solution must lie in $M$. The preprocessing time for this step is $O(n \log n)$.

Now, for the line: $c_i \cdot x + y = 0$, you need to find the point in $M$ that is farthest from the line. One such algorithm with preprocessing time of $O(n \log n)$ and query time of $O(\log^{2}n)$ is given here. Note that this algorithm is for finding the closest point. The farthest point from $c_i \cdot x + y$ is the same as the closest point from the line: $c_i \cdot (x-t) + (y-t) = 0$ where $t = \max_i \{x_i\} + \max_{i} \{ y_i\}$