Timeline for General form of amount of triangles that can be formed in an MxN point lattice
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2015 at 4:42 | comment | added | Brendan Murphy | 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$. | |
| Feb 16, 2010 at 8:27 | comment | added | Douglas Zare | I added the number-theory tag, as this is more of a number theory problem than a combinatorial one. | |
| Feb 16, 2010 at 8:26 | history | edited | Douglas Zare |
edited tags
|
|
| Feb 15, 2010 at 23:06 | answer | added | Gerry Myerson | timeline score: 8 | |
| Feb 15, 2010 at 17:48 | comment | added | domotorp | 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. | |
| Feb 15, 2010 at 17:26 | answer | added | HenrikRüping | timeline score: 0 | |
| Feb 15, 2010 at 17:19 | comment | added | Manuel Araoz | 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. | |
| Feb 15, 2010 at 15:51 | history | edited | Harry Gindi | CC BY-SA 2.5 |
edited title
|
| Feb 15, 2010 at 14:40 | history | edited | Steve Huntsman |
removed spurious tag
|
|
| Feb 15, 2010 at 14:39 | comment | added | Steve Huntsman | The answer is given by taking an appropriate binomial coefficient and then subtracting the number of colinear three-point configurations. | |
| Feb 15, 2010 at 13:27 | history | asked | Manuel Araoz | CC BY-SA 2.5 |