Finding the point that maximizes a linear function Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i &gt; 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 &quot;closest&quot; 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.
Another Answer:

Find the 2D maximal point set. Let us call it the set $M$.
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.