Given a triangulation (geometry), are there known algorithm in finding common side of triangles, that is O(N) or better?

enter image description here


1 Answer 1


If you know the number of edges and triangles, you could raster through a list of your triangles and create a triangle-to-edge map $(\mathcal{O}(N_{tri}))$ and simultaneously create the inverse map, which will give you the two triangles that share an edge. A naive search of that list for the right triangle-pair will be $\mathcal{O}(N_{edge})$, where $N_{edge}$ will at worst be $3 \cdot N_{tri}$. Of course, this all assumes you have a method for computing a unique ID for each edge in the graph.

  • $\begingroup$ Assuming you don't have a very large mesh (twice the number of vertices $2N_v < $ max unsigned long int value), since each edge is identified by two vertices $v_1, v_2$, a unique edge ID can be given by $v_1 + v_2 N_v$. $\endgroup$
    – Jesse Chan
    Jun 21, 2015 at 14:44
  • 2
    $\begingroup$ In fact, the unordered tuple $(v_1,v_2)$ is also a unique ID, without the restriction on the size of the integers. $\endgroup$ Jun 21, 2015 at 16:07
  • $\begingroup$ Good point. You could then sort the tuples $(v_1,v_2)$ (using std::sort and a comparison operator). If you attach an element ID to each tuple, matching elements will come up as sequential pairs of tuples in this list. $\endgroup$
    – Jesse Chan
    Jun 21, 2015 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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