<p><strong>Another Answer:</strong></p>
<ol>
<li>Find the <a href="https://en.wikipedia.org/wiki/Maxima_of_a_point_set" rel="nofollow noreferrer">2D maximal point set</a>. Let us call it the set <span class="math-container">$M$</span>.</li>
<li>Find the convex hull of <span class="math-container">$M$</span>. Let us call it <span class="math-container">$co(M)$</span>.</li>
</ol>
<p>The preprocessing time for the two step is <span class="math-container">$O(n \log n)$</span>.</p>
<p>Now, for the line: <span class="math-container">$c_i \cdot x + y = 0$</span>, you need to find the point in <span class="math-container">$M$</span> that is farthest from the line. That point must lie on the boundary of <span class="math-container">$co(M)$</span>. 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 <span class="math-container">$O(\log n)$</span> time using binary search.</p>
<hr />
<p><strong>Explanation</strong>: Firstly note that <span class="math-container">$c_i, x_i,$</span> and <span class="math-container">$y_i$</span> are all positive numbers. Therefore, if <span class="math-container">$(x_b,y_b)$</span> dominates <span class="math-container">$(x_a,y_a)$</span>, i..e, <span class="math-container">$x_b \geq x_a$</span> and <span class="math-container">$y_b \geq y_a$</span>, then, it implies <span class="math-container">$c_i \cdot x_b + y_b \geq c_i \cdot x_a + y_a$</span>. Therefore, an optimal solution must belongs to <span class="math-container">$M$</span>.</p>
<p>Now, let us call the line <span class="math-container">$c_i \cdot x + y = 0$</span> as <span class="math-container">$\ell$</span>.
The distance of a point <span class="math-container">$(x_a,y_a)$</span> from <span class="math-container">$\ell$</span> is: <span class="math-container">$\frac{|c_i \cdot x_a + y_a|}{\sqrt{c_{i}^{2}+1} }$</span>. Since <span class="math-container">$c_i, x_a,$</span> and <span class="math-container">$y_a$</span> are all positive numbers, and the denominator <span class="math-container">$\sqrt{c_{i}^{2}+1}$</span> is the same for all the points, a point maximizes the value <span class="math-container">$c_i \cdot x + y$</span> if and only if it farthest from line <span class="math-container">$\ell$</span>. Therefore, we need to find the point in <span class="math-container">$M$</span> that is farthest from line <span class="math-container">$\ell$</span>. The rest of the procedure is simple.</p>
<p>In fact, we do not even need to compute <span class="math-container">$M$</span>. We could have directly considered the original set of points to compute the convex hull. But computing <span class="math-container">$M$</span> would only decrease the query time complexity.</p>

CC BY-SA 4.0
2021-05-30T09:29:59.680Z
@D.W. Thanks for checking the solution. I have added the explanation. I Hope, it answers your question.
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T17:42:16.870Z
2021-05-30T10:37:13.043Z
2021-05-30T10:37:13.043Z
Inuyasha Yagami
<p>Find the <a href="https://en.wikipedia.org/wiki/Maxima_of_a_point_set" rel="nofollow noreferrer">2D maximal point set</a>. Let us call it the set <span class="math-container">$M$</span>. The solution must lie in <span class="math-container">$M$</span>.
The preprocessing time for this step is <span class="math-container">$O(n \log n)$</span>.</p>
<p>Now, for the line: <span class="math-container">$c_i \cdot x + y = 0$</span>, you need to find the point in <span class="math-container">$M$</span> that is farthest from the line. One such algorithm with preprocessing time of <span class="math-container">$O(n \log n)$</span> and query time of <span class="math-container">$O(\log^{2}n)$</span> is given <a href="https://www.sciencedirect.com/science/article/pii/S0167865598000804?casa_token=1l3zjc89GdoAAAAA:w92X7mnJSJJhFPQnDP84Y-Ib_Nu-W55TTIbfU6wMikbwEVhQVNS5kzqx1gqzMwZOGA_0qvFz" rel="nofollow noreferrer">here</a>. Note that this algorithm is for finding the closest point. The farthest point from <span class="math-container">$c_i \cdot x + y$</span> is the same as the closest point from the line: <span class="math-container">$c_i \cdot (x-t) + (y-t) = 0$</span> where <span class="math-container">$t = \max_i \{x_i\} + \max_{i} \{ y_i\}$</span></p>

CC BY-SA 4.0
2021-05-29T17:20:38.230Z
c_i.x + y = 0 always passes through the origin so the second result of the second paper is applicable here. So I can find the maximizing point in O(log^2 N) time.
karmanaut
CC BY-SA 4.0
2021-05-29T17:22:51.543Z
Yup. You are right!
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T17:24:48.787Z
Umm but we want the closest point from $c_i \cdot (x-t) + (y-t) = 0$....
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T17:25:19.170Z
That is also okay, since line always passes through $(t,t)$. right!
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T17:34:11.350Z
I believe, it can also be done in $O(\log n)$ time using binary search if we make a convex hull of the point set $M$.
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T17:42:23.750Z
Yeah I think O(log N) is doable. We start with the point with largest x (and then largest y for this x) in M. Let say this point is p_1. Now we can show that going up the convex hull is always a good idea to the next point p_2, if slope of p_1 and p_2 is larger than c_i. This will ensure that any decrease in x is more than compensated by the increase in y when going to p_2, always increasing the objective function value. This process terminates when we reach a line segment with same slope or just smaller slope than c_i -- which is what binary search will help us find.
karmanaut
CC BY-SA 4.0
2021-05-29T17:43:44.160Z
@karmanaut Agreed. I have added another answer similar to the one you are saying.
Inuyasha Yagami
CC BY-SA 4.0
2021-05-29T16:39:18.620Z
2021-05-29T17:23:28.097Z
2021-05-29T17:23:28.097Z
Inuyasha Yagami
<p>Consider <span class="math-container">$N$</span> two-dimensional points of the form <span class="math-container">$(x_i, y_i)$</span> where all <span class="math-container">$x_i, y_i &gt; 0$</span> are positive integers. We will be given a workload of queries <span class="math-container">$Q = \{c_1, \dots, c_k\}$</span> where for each <span class="math-container">$c_j \in Q$</span> (a positive integer), we need to find the point that maximizes the linear function <span class="math-container">$c_j \cdot x+y$</span>.</p>
<p>Ideally, I would like to preprocess all the points in at most <span class="math-container">$O(N \log N)$</span> time and then answer the query for each <span class="math-container">$c_j \in Q$</span> in <span class="math-container">$O(\log N)$</span> (or maybe even constant) time.</p>
<p>I feel there is such an algorithm where I can sort the points by <span class="math-container">$x_i$</span> and/or <span class="math-container">$y_i$</span> 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?</p>
<p>Edit : A fellow graduate student gave the following idea - constructing a convex hull of the <span class="math-container">$N$</span> 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 <span class="math-container">$-c_j$</span> will identify the point that maximizes the linear function <span class="math-container">$c_j x + y$</span>. I think this works but will verify the details tomorrow. My sleep will be ruined if there is a bug.</p>

CC BY-SA 4.0
2021-05-30T00:34:26.577Z
This is very standard in computational geometry. I don't think it is a research-level question.
David Eppstein
<ds.algorithms><optimization><ds.data-structures>
Finding the point that maximizes a linear function
karmanaut
# Finding the point that maximizes a linear function

(Asked by: username_0 on 2021-05-29)

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.

**Tags:** ds.algorithms, optimization, ds.data-structures
> **Comments:**
> **username_1**: This is very standard in computational geometry. I don't think it is a research-level question.  

---

## 2 answers

### Answer by username_2 on 2021-05-29. Score: 2 | Accepted answer

**Another Answer:**

1. Find the [2D maximal point set](https://en.wikipedia.org/wiki/Maxima_of_a_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.

> **Comments:**
> **username_2**: @D.W. Thanks for checking the solution. I have added the explanation. I Hope, it answers your question.  

---

### Answer by username_2 on 2021-05-29. Score: 0

Find the [2D maximal point set](https://en.wikipedia.org/wiki/Maxima_of_a_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](https://www.sciencedirect.com/science/article/pii/S0167865598000804?casa_token=1l3zjc89GdoAAAAA:w92X7mnJSJJhFPQnDP84Y-Ib_Nu-W55TTIbfU6wMikbwEVhQVNS5kzqx1gqzMwZOGA_0qvFz). 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\}$

> **Comments:**
> **username_0**: c_i.x + y = 0 always passes through the origin so the second result of the second paper is applicable here. So I can find the maximizing point in O(log^2 N) time.  
> **username_2**: Yup. You are right!  
> **username_2**: Umm but we want the closest point from $c_i \cdot (x-t) + (y-t) = 0$....  
> **username_2**: That is also okay, since line always passes through $(t,t)$. right!  
> **username_2**: I believe, it can also be done in $O(\log n)$ time using binary search if we make a convex hull of the point set $M$.  
> **username_0**: Yeah I think O(log N) is doable. We start with the point with largest x (and then largest y for this x) in M. Let say this point is p_1. Now we can show that going up the convex hull is always a good idea to the next point p_2, if slope of p_1 and p_2 is larger than c_i. This will ensure that any decrease in x is more than compensated by the increase in y when going to p_2, always increasing the objective function value. This process terminates when we reach a line segment with same slope or just smaller slope than c_i -- which is what binary search will help us find.  
> **username_2**: @karmanaut Agreed. I have added another answer similar to the one you are saying.  

---

