2
$\begingroup$

First please let me introduce some terminology in order to avoid misunderstandings (forgive me if it is a bit tedious).

Consider a collection of finite number of planar, consecutive line segments, with no internal intersections and forming a simple , closed curve. As such a curve, it separates the plane in one bounded and one unbounded domain. We consider a $n$-polygon to be such a curve including the bounded domain. The perimeter of $P$ is the above mentioned line.

A triangulation (without adding extra vertices) of a polygon $P$ is its partition into a set of triangles that have the same vertices with $P$ and these triangles have pairwise non-intersecting interiors and also their union is $P$.

Now comes the question: Is it possible to triangulate any polygon?

After searching a bit, I found that this is just a corrollary of the famous 2 -Ear Theorem by Max Dehn which gives an afformative answer.

But now I would like to demonstrate my idea- (if proof) and you to tell me if it is ok or not.

Proof (by Induction). The case for $3$- polygons (triangles) is trivial. Consider now that all $3,4,...n-1$-polygons can be triangulated and $P$ is an $n$ -Polygon. Then $P$ should have at least one convex angle $ABC$, otherwise $P$ is unbounded.Inside angle $ABC$ can be some other vertices too. Select those that have the least Euclidian distance from vertice $B$. And from those vertices select one, lets say $B'$ that is on the outmost left (or right). See picture below:enter image description here Now the segment $BB'$ is a diagonal of $P$ and the perimeter of $P$ is divided into $2$ lines $BC...B'$ and $BB'...A$, with lengths $l,m<n-1$ respectively. Clearly $n=m+l$. Then the polygons $BC...B'$, $BB'...A$ are $l+1, m+1<n$ and by the assumption of the induction they can be triangulated. So can be $P$.

Is it oK ? Thanks.

EDIT $1$

After some really usefull comments of @Jaap Scherphuis, I edit this question as follows:

In the proof instead of selecting the nearest and outmost right (or left) vertice, take a semi line from vertice $B$ and segment $BC$. Rotate this semi line untill it reaches a vertex (it maybe more than one). From all such vertices select this one which is closer to vertice $B$ (Let' s say $b$). The rest of the proof remains the same.

enter image description here

$\endgroup$
7
  • 2
    $\begingroup$ You have 3 vertices at equal distance to B. Imagine that B' and the other outermost vertex are both a tiny bit further away, so that the middle one is the only closest vertex left. This will not give you a diagonal. Instead of choosing one of the closest vertices, try choosing the vertex with the highest y-coordinate (assuming the figure is rotated such that B has a higher y-coordinate than A or C). $\endgroup$ Oct 10, 2023 at 15:50
  • $\begingroup$ There is the possibility that no such $B'$ exist. For example, consider the quadrilateral $PQRS$ with $P = (0, 0)$, $Q = (0, 1)$, $R = (1, 0)$, and $S = (1000, -1)$. If you select $\angle PQR$ as the convex angle, there is no other vertex "inside" this angle. $\endgroup$
    – VTand
    Oct 10, 2023 at 16:03
  • 1
    $\begingroup$ @VTand Yes, the case without vertices in ABC was skipped in the proof, but that is the almost trivial case because AC is then a diagonal. $\endgroup$ Oct 10, 2023 at 16:05
  • 1
    $\begingroup$ I think that to get the proof watertight when using y-coordinates, you need to rotate the figure so that AC is horizontal. Equivalently, instead of y-coordinates you can sweep a line across ABC until it reaches an interior vertex or reaches AC. $\endgroup$ Oct 10, 2023 at 21:15
  • 1
    $\begingroup$ Your new version is also not guaranteed to work since there may be edges connecting to a vertex to the left of BC which intersect your proposed diagonal bB. See this picture for example. You can instead sweep a semi-line around C, starting from CB and ending at CA or the first other vertex you encounter. If you encounter several vertices simultaneously, it does not matter which of them you choose. $\endgroup$ Oct 15, 2023 at 18:33

2 Answers 2

1
$\begingroup$

Given a polygon, the first step is to determine the extrema vertices. Can be done along the $X$ or $Y$ axes. Then we can choose one to begin the process. Lets begin with vertex $B$. This vertex opens a region from left to right, limited with by segments linking it to the nearest companions $C, A$. Note that the sequence $A\to B\to C$ is oriented CCW (counterclockwise). The next step is to verify if the triangle $CBA$ contains any of the remaining vertices. If not, the vertex $B$ is eliminated and a first triangulation is obtained: otherwise, the process continues counterclockwise to the next vertex $C$. Now considering the sequence $B\to C\to ?$ we can observe that it is CW oriented so we jump until the three corresponding vertices are CCW oriented, repeating the eliminate/non eliminate process, until the number of vertices is less or equal to $3$. Included three triangulations obtained with this method.

enter image description here

enter image description here

enter image description here

Follows the action sequence when applying the procedure in the first example. In dotted red, the remaining vertices after a new triangle classification. In this case we choose as the first vertex, the rightmost vertex.

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

$\endgroup$
5
  • $\begingroup$ Thanks for the answer +1. If the angle $B$ is non convex how the region is defined? $\endgroup$
    – dmtri
    Oct 21, 2023 at 5:17
  • $\begingroup$ Please. See the sequence included. The angle $B$ doesn't matter. $\endgroup$
    – Cesareo
    Oct 21, 2023 at 12:18
  • $\begingroup$ Hi again. I think it is enough to find just one angle CCW without interior vertices because then the remaining polygon would have 1 less verice and by induction it can be triangulated. $\endgroup$
    – dmtri
    Oct 21, 2023 at 14:36
  • $\begingroup$ Also some points that I do not get in the algorithm of your post: 1. What do you mean by Extrema Vertices? (Extrema vertice is such that does not belong to the convex hull of the remaining vertices?) 2. Does the algorithm goes like this: 1st Step. Find an extrema vertice, let's say this is $B$ (comment: extrema plays any role here?). If the triangle $ABC$ is CCW and has no other vertices inside then the algorithm stops as the diagonal $AC$ is inside the polygon. otherwise continue to: $\endgroup$
    – dmtri
    Oct 21, 2023 at 14:36
  • $\begingroup$ 2nd Step. Find the next CCW Angle that has no interior vertices. (how do we know that there is one ? and so the algorithm is finite?). Thanks again. $\endgroup$
    – dmtri
    Oct 21, 2023 at 14:36
0
$\begingroup$

In order to find a vertex inside the angle area $ABC$ we can select one that is closer to the side $BA$ (or $BC$). Lets say this is $M$ and it is always exist as the sides are of finite number. Now draw a parallel line $l$ to $BA$ and passes from $M$. Then between $BA$ and $l$ should be no other vertices and so the line segment between points $M$ and $B$ is inside the polygon. enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .