3
$\begingroup$

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to the following subproblem:

Let $A,B,P,$ and $Q$ be a group of 4 nodes, with coordinates $(x_A,y_A),(x_B,y_B)$,etc... such that:

  • $x_A$ and $x_P$ are less than both $x_B$ and $x_Q$
  • $y_A$ and $y_B$ are greater than $y_P$ and $y_Q$.

Let there be an arbitrary cluster of nodes contained within the quadrilateral formed by $A,B,P,$ and $Q$. Find a pair of paths $A\rightarrow B$ and $P\rightarrow Q$ such that:

  • Every node in the cluster is hit by exactly one of the two paths
  • The two paths have the minimum possible total (Euclidean) length
  • The two paths do not intersect
  • The paths always increase in $x$. That is, if we enumerate path $A\rightarrow B$ as $\{A,(x_1,y_1),(x_2,y_2), ...(x_n,y_n),B\}$, then $x_i<x_j$ for $0<i<j\leq n$. Also, $x_A<x_1$ and $x_n<x_B$. This property must hold for the $P\rightarrow Q$ path as well.

It is also worth mentioning that no two nodes in the entire problem will have the same $x$ coordinate.

I'm positive some geometric trick will play a huge role in finding the solution. Keep in mind this is just a subproblem and a solution to this in $O(n^2)$ will still be helpful - though I'm hoping for $O(n\log n)$.

Here's an example problem for clarity:

Sample Problem

Any solutions or even helpful ideas are always appreciated. Diagrams are also very much appreciated.

Finally, for added clarity, here is what a sample solution might look like:

Sample Solution

Improve this question
$\endgroup$
2
  • $\begingroup$ To aid with intuition, suppose we look at the special case where $ABQP$ form an axis-aligned rectangle. Is it guaranteed that, for the optimal solution, every point on the $A\to B$ path will be higher (have a larger $y$-coordinate) than every point on the $P\to Q$ path? Can you find a proof or counterexample? If this is true, then there's a chance it might help find faster algorithms.... $\endgroup$
    – D.W. ♦
    May 15, 2015 at 4:48
  • $\begingroup$ @D.W. Counterexample: Try drawing a 'W' shaped path between A and B, and assume the path is very dense with nodes (each node 'u' units apart - assume u to be very small).Now draw another path that comes up from P to just under the centerpoint of the 'W', whilst staying more than 'u' units away from the 'W', then connects down to Q. Assume the P->Q path is equally dense. The peak of the P->Q path will reach up inside the W and vertically surpass the bottom points of the 'W'. The path will be optimal b/c each node will require the absolute minimum cost possible to connect (u units). $\endgroup$
    – A Frayed Knot
    May 15, 2015 at 19:45

1 Answer 1

Reset to default
2
$\begingroup$

Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$.

In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$. To solve each subproblem, you only have to look at the solution to two subproblems: in particular, to $(Z,P')$ and $(A',Z)$, where $Z$ is the point immediately to the left of the rightmost of $A',P'$. Therefore, each subproblem can be solved in $O(1)$ time. As there are $O(n^2)$ subproblems, the $O(n^2)$ running time follows immediately.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If I'm not mistaken, I believe "immediately left of the rightmost" should actually be "immediately right of the rightmost"? Because the left of the rightmost would already be contained in a path in the previous subproblem. Or am I misunderstanding? $\endgroup$
    – A Frayed Knot
    May 15, 2015 at 5:20
  • $\begingroup$ @KyleMcCormick, I think what I wrote was correct. Given the solution to subproblem $(Z,P')$, you can extend it to a solution to subproblem $(A',P')$ by adding the edge $Z\to A'$ to the end of the first path. Given a solution to subproblem $(A',Z)$, you can extend it to a solution to subproblem $(A',P')$ by adding the edge $Z \to P'$ to the end of the second path. Thus, given the solutions to subproblems $(Z,P')$ and $(A',Z)$, you can compute the best solution to subproblem $(A',P')$. This is a d.p. algorithm that goes "left-to-right". (You could also solve it "right-to-left", I guess.) $\endgroup$
    – D.W. ♦
    May 15, 2015 at 5:58
  • $\begingroup$ You can in fact speed this solution up further by looking at the "changeover points." Let's define a subproblem by a turning point $P'$, which has a similar definition to the above answer, with $A'$ equal to the point just before $P'$ when sorted by x-coordinate. To answer this subproblem, we have to consider all possible next turning points (this time, specified by $A'$, with $P'$ being the point just before $A'$). Both these DPs can be solved in linear time, by tracking the best turning point for each suffix of points. $\endgroup$
    – KKOrange
    Oct 8, 2019 at 16:57
  • $\begingroup$ The non-self intersecting requirement is redundant, since there is always an optimal solution where the paths do not cross. See math.stackexchange.com/questions/928069/… $\endgroup$
    – KKOrange
    Oct 8, 2019 at 16:59

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.