1
$\begingroup$

I'm pretty sure this is a graph theory problem :

I'm trying to figure out a formula for the number of triangles that can be created from n distinct points in the (Euclidean) Plane such that no 2 lines cross each other (if a formula is possible).

For my purposes, we can assume that no 3 points are on the same line, and of course, we can assume n > 2. Also, points, and lines, can be used for more than 1 triangle, but, as mentioned, lines cannot cross.

Is there a formula for this?

Also, a related question : Given those n points, and the triangles formed by them, is there a formula to find the number of distinct segments forming those triangles? (So, for 2 triangles that share 1 side, there are 5 segments, etc.)

Thanks in advance!

$\endgroup$
1
$\begingroup$

This follows from Euler's formula for planar graphs: $V-E+A=1$. Here $V$ is the number of vertices (points), $E$ the number of edges (lines) and $A$ the number of connected areas (not counting the exterior of the planar graph). Split $V$ as $V=V_1+V_2$ where $V_1$ is the number of points on the boundary of the convex hull of all points and $V_2$ is the number of points in the interior of the convex hull. If every connected area is a triangle then the key observation is $$E=\frac{3A+V_1}{2}$$ so from Euler's formula it follows that $A=V_1+2V_2-2$.

$\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.