This is broadly how I was thinking about it, but I don't have an intuition for why there would be a recurrence relation involving the factors of Q(m, n). What made you think of attacking it that way?
Also, note that Q(m, n) = Q(n, m), so if we can calculate Q(m + 1, n) as a function of Q(m, n) we can also do it for Q(m, n + 1). Calculating Q(m + 1, n) as a function of Q(m, n) doesn't seem complicated if it weren't by the rules "no straight angles and does not self-intersect". Maybe it can be done with some combinatorics, but seems beyond my skill. Also, expressing it in terms of combinations may also simplify calculation of rest of division.
If such relation can be found, I think the problem may be easily solved.
each valid quad of Q(m, n) moving an edge to another possible one in the new line +
each valid quad of Q(m, n) moving a vertex to the new line +
the same thing moving each unique valid quad of Q(m, n) to the new line.
The number of new possible vertices on the new line is (m + 1) . The problem is: moving each vertex of each quad that can be generated in Q(m, n) to the new possible vertices may generate quads that break the rules.
Finding a way to calculate both terms looks like good progress.
Hmmmm.... New ideas coming... Maybe we don't have to care about crossings: any crossing can be solved by reordering the vertices, so, all we have to care about is the number unique vertices positions!
I still don't know how to avoid straight angles though.
Consider U(m, n) as the number of new unique forms possible for Q(m, n). I'm not sure, but it looks like:
U(1, 1) = 1
U(m + 1, n) = U(m, n) * (n + (n+1)*n/2) - X
U(m, n + 1) = U(m, n) * (m + (m+1)*m/2) - X
If we can find X, then, I think Q is given by:
Q(m, n) = m*n*U(1, 1) + (m-1)*(n-1)*U(2, 2) + (m-2)*(n-2)*U(3, 3) +...+ 1*1*U(m, n)Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some triangles have two edges in which a point can be inserted to create a quadrilateral, while others only have one.
The difficulty is finding those terms, though…
Also, I think my previous formula is wrong. Maybe it is the sum of:
(m - i + 1)*(n - j + 1)*U(i, j)
But maybe it is still wrong because U(i, j) will re-count combinations from U(i - 1, j) and U(i, j - 1)...
Argh! This is complicated! I think I'll have to revisit it if I ever have a good idea.
For example, if you wanted to use DP to compute all-pairs-shortest-paths (Floyd-Warshall), you add a third parameter to the DP state ((f(u, v, k)).