3
$\begingroup$

Triangulation of a simple polygon $P$ is a decomposition of $P$ into triangles by a maximal set of non-intersecting diagonals. We also know that triangulation of a polygon is not neccessarily unique. The question (taken from Computational Geometry in C by J. Rourke):

Which polygons have the fewest number of distinct triangulations? Can polygons have unique triangulations? Which polygons have the largest number of distinct triangulations?

Note: I've already answered the second part by drawing a convex 4-gon with only 1 possible diagonal. The problem is the other two parts.

$\endgroup$
4
  • 1
    $\begingroup$ Look at Catalan numbers, for example: math.umn.edu/~reiner/Classes/Catalan.pdf $\endgroup$
    – HEKTO
    Oct 15 '16 at 18:04
  • 1
    $\begingroup$ It seems that you can find (partial) answers here. $\endgroup$
    – mathlove
    Oct 5 '18 at 5:42
  • $\begingroup$ @mathlove Thanks! How can I end the bounty? $\endgroup$
    – Perceptual
    Oct 5 '18 at 6:00
  • $\begingroup$ @Arman Malekzadeh: See here. $\endgroup$
    – mathlove
    Oct 5 '18 at 6:04
2
$\begingroup$

Number of triangulations of convex n-gon is the (n − 2)nd Catalan number. This is maximum possible number of triangulations.

Let's consider following n-gon:

(n, 0), (0, 0), (1, 1), (2, 4), ..., (i, i^2), ..., (n - 2, (n - 2)^2).

All vertices of the polygon except first belong to parabola.

Each triangulation of n-gon has n - 3 diagonals.

The only convex vertices are first, second and last. Any diagonal with both ends on the parabola is invalid (lies outside of polygon). So we have only n - 3 valid diagonals connecting vertices: (1, 3), (1, 4), ..., (1, n - 1). These diagonals make up one and only one triangulation.

$\endgroup$
1
  • 2
    $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Dec 20 '21 at 19:45
-1
$\begingroup$
  1. Convex polygons (ones with all internal angles less than $180^\circ$) have minimal polygons equal to the number of vertices minus 2.

enter image description here

Note: While these are all regular (same lengths and angles) they don't have to be. (It was just easier to draw.)

  1. Any concave corners increase the number of polygons required. Many kinds of polygons have maximal triangles. Easy to draw examples would be stars (but lots of convolutions of these basic shapes are possible).

enter image description here

  1. This is a very broad question and whole books could be written about this as there are so many cases to cover. I'd recommend reading up on computer graphic triangulation and computer graphic primitives.
$\endgroup$
2
  • 1
    $\begingroup$ My question was about number of ways one can triangulate a polygon. Your answer is about number of triangles made by a triangulation... $\endgroup$
    – Perceptual
    Oct 9 '16 at 8:49
  • $\begingroup$ Oh right. I misread it. I don't think there is any short answer to the question you've asked. I'll leave this here for now and delete if you want. $\endgroup$
    – Ian Miller
    Oct 9 '16 at 11:21

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.