1
$\begingroup$

Given a 3x3 grid:

1 2 3
8 9 4
7 6 5

We find 126 distinct sets of 4 points $$\binom{9}{4}$$

There are 8 cases such that when the points are connected with a line in clockwise direction, one point (in this case, 9) is contained by angle formed from joining the other three points with a line:

{1,3,6,9}, {1,4,6,9}, {1,4,7,9}, {2,4,7,9},

{2,5,7,9}, {2,5,8,9}, {3,5,8,9}, {3,6,8,9}.

i.e.enter image description here, where {1,4,7,9} contains 9.

For a grid of any m and n, how can we determine the number of sets for which such a condition holds? So, the number of sets across all $$\binom{mn}{4}$$

Where one point is inside angle formed by connecting the other 3 members of the set.

$\endgroup$
  • $\begingroup$ What exactly do you mean when you say one is contained by the other three? $\endgroup$ – Arthur Jun 15 '15 at 17:13
  • $\begingroup$ Updated answer, adding illustration @Arthur $\endgroup$ – Calvin Froedge Jun 15 '15 at 17:14
  • $\begingroup$ Do you want the answer for a specific fixed "middle" element in your $m \times n$ grid, or do you want the sum of counts of all solutions over all choices for "middle" element? And if the latter, what if a triangle contains more than one "middle" point? Do you want that to just count as 1, or do you want to multiply by the number of middle points? $\endgroup$ – user2566092 Jun 15 '15 at 17:16
  • $\begingroup$ So you want the number of sets of four points in a rectangular grid that don't make a convex (degenerate?) quadrilateral? $\endgroup$ – Arthur Jun 15 '15 at 17:19
  • $\begingroup$ @Arthur Based on the example, it seems like the "middle point" must be in the strict interior, e.g. (2,4,6,9) wasn't listed as a solution. $\endgroup$ – user2566092 Jun 15 '15 at 17:21
0
$\begingroup$

Pick's theorem will tell you for a grid how many interior grid points you have inside a given triangle, in terms of the volume (easy to compute) and number of boundary points on the triangle (also easy to compute by computing for each side, the GCD of coordinates of the vector connecting one vertex to another). Also the answer is translation and rotation and reflection invariant since you are working on a grid. So this reduces a seemingly ${{mn} \choose 4}$ complexity calculation to one that is $O({{mn} \choose 2})$, basically by assuming one vertex is $(1,1)$ and the other vertices are in the upper-right. It's still not as good as an explicit formula but it can at least handle values of $mn$ that are the square of the values of $mn$ that you could previously handle by brute force.

$\endgroup$
  • $\begingroup$ Well, you don't have to do every choice of ${{mn} \choose 3}$ triangles, based on the symmetries, but yes, basically you have to do $O({{mn} \choose 2})$ triangles this way and evaluate them individually and then multiply by the number of similar triangles you can get by translation/rotation/reflection. So it won't scale forever without a more explicit formula, but at least you can solve bigger cases than brute force. And even without symmetries, you can count the number of interior points for each of the ${{mn} \choose 3}$ triangles easily with Pick's theorem. $\endgroup$ – user2566092 Jun 15 '15 at 17:47
  • $\begingroup$ Any ideas how to develop an explicit formula? Do you think one exists or is possible? $\endgroup$ – Calvin Froedge Jun 15 '15 at 17:48
  • $\begingroup$ Is it fair to say there will be a recurrence relation between the size of the grid and the number of triangles with interior grid points? $\endgroup$ – Calvin Froedge Jun 15 '15 at 17:50
  • $\begingroup$ @CalvinFroedge I'm not sure. If you increase $m$ or $n$ then it's possible you'll get new triangles with interior points where the new triangles have side slopes that weren't possible for previous $m$ and $n$. I have to think more, but I'm guessing this problem is fairly hard. $\endgroup$ – user2566092 Jun 15 '15 at 17:58
  • $\begingroup$ @CalvinFroedge I'd recommend setting $m = n$ and brute forcing the answer for a decent number of values of $n$ and then checking the sequence of counts you get against the Online Encyclopedia of Integer Sequences (OEIS). $\endgroup$ – user2566092 Jun 15 '15 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.