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

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.

StackExchange Computer Science Q#42569, answer score: 2