5
$\begingroup$

I've been searching for the answer for many years, both by researching by myself and reading about the subject. Now I'm wondering if this has a solution.

The problem can be stated as follows.

Given a M x N grid of points, how many triangles with vertices in the grid can be formed? Note that you can't select two points that coincide or three collinear points because that wouldn't conform a triangle (area would be 0)

OK, I know a bit of programming and could manage to code a program that solves this, but would REALLY like to know if there is a general form depending on M and N. I suspect it has to do with prime numbers... (Perhaps I totally missed heheh)

Thanks for your time! Manuel

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The answer is given by taking an appropriate binomial coefficient and then subtracting the number of colinear three-point configurations. $\endgroup$
    – Steve Huntsman
    Commented Feb 15, 2010 at 14:39
  • 2
    $\begingroup$ Yeah, the thing is how many collinear three-point configurations to subtract. That's the real challenge. Think about it for a moment and you'll realize this is not as trivial as it may seem. $\endgroup$
    – Manuel Araoz
    Commented Feb 15, 2010 at 17:19
  • $\begingroup$ The question is equivalent to count the collinear triples, for which it is not hard to write up a summation but I donno whether an explicit formula would exist. $\endgroup$
    – domotorp
    Commented Feb 15, 2010 at 17:48
  • $\begingroup$ I added the number-theory tag, as this is more of a number theory problem than a combinatorial one. $\endgroup$
    – Douglas Zare
    Commented Feb 16, 2010 at 8:27
  • $\begingroup$ It follows from the Szemeredi-Trotter theorem that the number of collinear triples in a finite set of points $P\subseteq\mathbb{R}^2$ is $< C|P|^2 log|P|$ for some absolute constant $C$, assuming that no line is incident to more than $\sqrt{|P|}$ points. Thus if $P$ is an $N\times N$ grid, the number of collinear triples is $\lesssim N^4\log N$. $\endgroup$
    – Brendan Murphy
    Commented Feb 3, 2015 at 4:42

2 Answers 2

Reset to default
8
$\begingroup$

For the NxN case, at least, there is a literature. An entry point is sequence A000938 in the On-Line Encyclopedia of Integer Sequences.

Improve this answer
$\endgroup$
0
$\begingroup$

ok here is one answer, but I think, you already knew that:

so there are $\left((M+1)(N+1)\atop 3\right)$ possible triangles an we have to subtract the number of triangles, which are degenerated. Every degenerated triangle is given by a choice of 2 points $P=(x,y),P'=(x',y')$ and a choice of a lattice point on the segment from $P$ to $P'$. Let $R:=gcd(x-x',y-y')$. There should be exactly $R+1$ points on that line, so we get at least a method, how a computer programme could compute that number.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @HenrikRüping hey can you explaine more about R ? $\endgroup$
    – user66661
    Commented Feb 3, 2015 at 3:02
  • $\begingroup$ Should it be $\ R-1\ $ points ( **inside** interval $\ PP'$)? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 3, 2015 at 3:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .