4
$\begingroup$

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.

One example

Is there, or can someone develop ;), an algorithm to answer this?

Feel free suggesting and making up data representations for the problem.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Certain regular configurations do have special formulas. But this isn't true for a general configuration. $\endgroup$ – Joe Z. Nov 23 '14 at 8:09
  • $\begingroup$ Which formula are you referring to? Do you mean that C implementation? $\endgroup$ – d'alar'cop Nov 23 '14 at 8:12
0
$\begingroup$

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:

  • Checking if $a$ and $b$ are connected by a line before selecting $c$
  • Looping over the lines (edges) instead of the vertices might be more efficient, but not as intuitive
$\endgroup$

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.