There is a type of puzzle where one needs to count triangles in a figure, generally a large triangle full of lines which create smaller ones.
Is there, or can someone develop ;), an algorithm to answer this?
Feel free suggesting and making up data representations for the problem.
This has been discussed at StackOverflow.
Everything rests on seeing that the problem you are describing is a graph problem. So, everything should begin with expressing your shape as a graph. There is an implementation in C which gives an example of the representation as a graph and which performs the task of calculating how many triangles there are.
Someone pointed at this paper, saying that the problem is computationally as difficult as Matrix Multiplication. Essentially the time complexity will be $O(n^3)$.
One of the answers there by evhen13 outlines the following candidate algorithm which is recursive in nature:
You will need depth first search. The algorithm will be:
1) For the current node ask all unvisited adjacent nodes
2) for each of those nodes run depth two check to see if a node at depth 2 is your current node from step one
3) mark current node as visited
4) on make each unvisited adjacent node your current node (1 by 1) and run the same algorithm
Here is a brute force algorithm in pseudo code:
Assumptions: we have the set of all the vertices $V$ (where two or more lines meet) and lines (edges in graph theory) between them.
For each vertex a in V
For each vertex b in V where b != a
For each vertex c in V where c != a or b
If there are lines connecting a<-->b, b<-->c, and c<-->a
and if these vertices are not all in a straight line, then they
form a triangle, so increment the triangle count
This is trivially $O(n^3)$.
There are some ways to prune this search by:
