3
$\begingroup$

Say I wish to form exactly two non-intersecting triangles using vertices of an $n$ sided polygon.

How many ways would there be of doing this?

The condition is that the vertices must be distinct. In other words, we cannot share vertices.

I have below an example of a 'good' set of triangles.

enter image description here

I am not even sure where to begin here.

$\endgroup$
  • $\begingroup$ To help you clarify your question: (1) if $n = 3$, you cannot do it, assuming your triangle vertices are also vertices of the polygon. (2) For quads, it's straightforward. Call the verts $ABCD$ in order. If, say, vertex $A$ is in the convex hull of the other three, then use $ACB$ and $ACD$; otherwise divide by any diagonal. (3) Your third paragraph asks a different question from the first two, since it asks how many ways there are to do something, rather than asking for SOME way to do the thing. Try to be really clear about what you want, so that we can better help you. $\endgroup$ – John Hughes Aug 31 '15 at 12:21
  • $\begingroup$ I have edited my question accordingly. $\endgroup$ – Trogdor Aug 31 '15 at 12:23
  • $\begingroup$ Your example shows a convex polygon; may we assume that the starting polygon is convex, or could it be arbitrary (like a "dart-shaped" 4-sided polygon)? $\endgroup$ – John Hughes Aug 31 '15 at 12:24
  • $\begingroup$ I had intended for the polygon to be convex and regular, cheers. $\endgroup$ – Trogdor Aug 31 '15 at 12:25
  • $\begingroup$ Also, suppose I divide a square by its diagonal into two triangles. Do you consider that they intersect or not? (i.e., are your triangles "closed" (include their edges) or "open"?) $\endgroup$ – John Hughes Aug 31 '15 at 12:25
5
$\begingroup$

Assumption : ( we consider that the circular configurations are not the same)

As I explained in a comment, the number of ways of forming two triangles in a polygon is either by choosing four points in the polygon ( and hence there is two shared points (vertices), one shared side), by choosing five points in the polygon ( there is one shared point) or by choosing 6 points in the polygon (In this case there is no shared vertices between the triangles ). The triangles can not share more than two vertices.

Now It's just a matter of calculations to get the following notes for an $n$-gone :

  • The number of hexagons (6 different points ) is ${n\choose 6}$ and for every hexagon we can draw in exactly 3 ways two triangles which does not share any vertices.(here I mean two pairs of triangles not ordered pairs and the same thing for the next notes)

  • The number of pentagons (5 different points ) is ${n\choose 5}$ and for every pentagon we can draw in exactly 5 ways two triangles which does share only one point.

  • The number of squares (4 different points ) is ${n\choose 4}$ and for every square we can draw in exactly 2 ways two triangles which does share only one side.

Finally the answer is :

$$\boxed{\quad 3{n\choose 6}+5{n\choose 5}+2{n\choose 4}\quad } $$

(If I misunderstood the problem feel free to point it out)

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I'm going to assume the following:

  1. Shared vertices are allowed.

  2. The division is into pairs of triangles, not ordered pairs, so that $(ABC, DEF)$ and $(DEF, ABC)$ are "the same". Furthermore, order of verts in a triangle doesn't matter, so that these are both the same as $(BAC, DEF)$.

With that in mind, let's let $K(n)$ be the number of ways to form a single triangle from a polygon with $n$ vertices. You should, I hope, be able to work this out, and let $S(n)$ be the number of ways of forming two nonintersecting triangles.

Each triangle (like the right-hand one in your picture), when excised from the polygon, leaves behind three smaller polygons, although in some cases (like the left-hand one in your picture), these smaller polygons are vacuous. The "other" triangle of the pair must lie in one of these three remainders, so you get a recurrence: for a fixed "first" triangle, there are $K(a) + K(b) + K(c)$ possible second triangless, where $a$, $b$, and $c$ are the sizes of the three "remainder" polygons. You need to sum these over all possible "first" triangles, and then divide your result by two to account for the arbitrariness of calling one triangle the "first" one.

That's a wicked ugly recurrence, but it's probably not hopeless to at least get a big-O bound in the numbers.

| cite | improve this answer | |
$\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.