6 ms·

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 m

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?

marcodiego 5y ago
Because it may allow us to use dynamic programming to calculate Q(m, n) and because some new quadrilaterals can be easily generated simply by moving edges and vertices to new spaces when m or n is increased. So, it seems natural for me to try to write Q(m + 1, n) as a function of Q(m, n). 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.
- deleted 5y ago
  [deleted]
- marcodiego 5y ago
  This made me think of... U(m, n) as the number of unique forms of Q(m, n). By unique forms, I mean forms that can't be obtained by simply translating previously found forms. Maybe it is easy to calculate Q(m, n) as a function of U(m, n) and maybe calculating U(m, n) as a function of U(m - 1, n) is a bit easier than calculating Q(m - 1, n).
marcodiego 5y ago
Note: Q(m + 1, n) = 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 edges on the new line is n * (n - 1) / 2 . The problem is: moving each edge of each quad that can be generated in Q(m, n) to the new possible edges may generate quads that break the rules. 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.
- tylerhou 5y ago
  It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top left hand corner. Then Q(m, n) = \sum_{i \in m, j \in n} f(m, n, 4). f also lends itself to a much easier recurrence.
  - marcodiego 5y ago
    For me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles. 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.
    - tylerhou 5y ago
      If you didn’t care about the restrictions, then the answer is N*M choose 4.
  - marcodiego 5y ago
    I think I've made some progress... When one line is added to the problem, it allows us to put 1 or 2 vertices there, so... 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 Where X is the number of invalid forms generated adding one or two vertices in the new line because of straight angles in diagonals. I'm considering only diagonals, because adding only one or two vertices in the new line will not align 3 vertices horizontally or vertically if all "previous forms" were valid. 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)
    - tylerhou 5y ago
      > If we can find X 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…

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?

marcodiego 5y ago

Because it may allow us to use dynamic programming to calculate Q(m, n) and because some new quadrilaterals can be easily generated simply by moving edges and vertices to new spaces when m or n is increased. So, it seems natural for me to try to write Q(m + 1, n) as a function of Q(m, n). 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.

deleted 5y ago
[deleted]
marcodiego 5y ago
This made me think of... U(m, n) as the number of unique forms of Q(m, n). By unique forms, I mean forms that can't be obtained by simply translating previously found forms. Maybe it is easy to calculate Q(m, n) as a function of U(m, n) and maybe calculating U(m, n) as a function of U(m - 1, n) is a bit easier than calculating Q(m - 1, n).

marcodiego 5y ago

Note: Q(m + 1, n) = 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 edges on the new line is n * (n - 1) / 2 . The problem is: moving each edge of each quad that can be generated in Q(m, n) to the new possible edges may generate quads that break the rules. 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.

tylerhou 5y ago
It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top left hand corner. Then Q(m, n) = \sum_{i \in m, j \in n} f(m, n, 4). f also lends itself to a much easier recurrence.
- marcodiego 5y ago
  For me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles. 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.
  - tylerhou 5y ago
    If you didn’t care about the restrictions, then the answer is N*M choose 4.
- marcodiego 5y ago
  I think I've made some progress... When one line is added to the problem, it allows us to put 1 or 2 vertices there, so... 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 Where X is the number of invalid forms generated adding one or two vertices in the new line because of straight angles in diagonals. I'm considering only diagonals, because adding only one or two vertices in the new line will not align 3 vertices horizontally or vertically if all "previous forms" were valid. 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)
  - tylerhou 5y ago
    > If we can find X 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…