1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is very standard in computational geometry. I don't think it is a research-level question. $\endgroup$ May 30 at 0:34
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @D.W. Thanks for checking the solution. I have added the explanation. I Hope, it answers your question. $\endgroup$ May 30 at 9:29
0
$\begingroup$

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\}$

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – karmanaut
    May 29 at 17:20
  • 1
    $\begingroup$ Yup. You are right! $\endgroup$ May 29 at 17:22
  • $\begingroup$ Umm but we want the closest point from $c_i \cdot (x-t) + (y-t) = 0$.... $\endgroup$ May 29 at 17:24
  • 1
    $\begingroup$ That is also okay, since line always passes through $(t,t)$. right! $\endgroup$ May 29 at 17:25
  • $\begingroup$ 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$. $\endgroup$ May 29 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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