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&lt;x_j$ for $0&lt;i&lt;j\leq n$. Also, $x_A&lt;x_1$ and $x_n&lt;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:
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.