# Minimum Length Hamiltonian Path Pair in O(n^2) or better

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:

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:

• 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.... – D.W. May 15 '15 at 4:48
• @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). – A Frayed Knot May 15 '15 at 19:45

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.
• @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.) – D.W. May 15 '15 at 5:58
• 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. – KKOrange Oct 8 '19 at 16:57