Polygon triangulation

There are two types of triangulation, one is the triangulation of polygons, and the other is the triangulation of plane point sets. What is discussed here is the triangulation of polygons.

Art Gallery Problem

How to guard the art gallery with the fewest guards and make every corner of the art gallery within the sight of the guards?
An equivalent question is: how many lamps are needed to fully illuminate an entire room.

Figure 1 Art Museum Problem

art gallery problem

naive upper and lower bounds

Abstract the art gallery into a polygon, then when there is a core in this polygon, obviously only one guard is needed to complete it.
Considering the worst case scenario, placing a guard on any vertex of the polygon can definitely be completed.
So the number of guards is $1$ arrive $n$ between.

Unfortunately, for general polygons, the problem of solving the minimum number of guards needed to complete the task is $NP$ of.

Chvátal Art Gallery Theorem

Abstract the art gallery into polygons and the guards into points.
For any number of sides, $n$ of polygons, requiring at most $floor rac{n }{3} floor$ One point will definitely be completely covered. And the existence of polygons does require $floor rac{ n}{3} floor$ points can be covered.

Figure 2 Art Museum Theorem

worst case scenario

As shown in the picture above, each tip requires a point of coverage. This scenario is the worst case scenario.

How to prove that there is no worse case scenario?

Fisk's short proof

Obviously for a triangle, you only need to place a point on one of its vertices to cover the triangle.
Introduce several non-intersecting diagonals to triangulate the polygon. A diagonal is defined as a line segment connecting a pair of vertices of a polygon.
It can be proved that the number of any vertex is $n$ A simple polygon has a triangulation that decomposes it into $n-2$ triangle.
Prove the idea using mathematical induction. Take any diagonal of the polygon and cut the polygon into the number of vertices: $m_1$ ， $m_2$ polygon, there are $m_1,m_2>2$ and $m_1+m_2=n+2$ , and based on the assumption: $n$ A simple polygon with vertices can be decomposed into $n-2$ triangle. So the number of triangles included is $(m_1-2)+(m_2-2)=n-2$ indivual.

After triangulating the polygon, a graph is formed $G$ , the point set is the vertex of the polygon, and the edge set is the union of the polygon's sides and diagonals. observe $G$ The dual diagram of , it is easy to see that it is a tree. So for $G$ It must be possible to perform triple staining.
For two adjacent triangles, the two non-overlapping points must be colored the same, and the three vertices of each triangle must correspond to the three colors one by one. Therefore, iterating repeatedly starting from any triangle can complete the three-coloring of the entire picture.

Figure 3 Art Museum Theorem

Three colors of vertices

Among these three colors, choose any one to complete the coverage. According to the pigeonhole principle, the most choice $floor rac{ n }{3} floor$ A point is enough.

The above is an approximate solution to the museum problem, pointing out that for any $n$ A simple polygon with points, although the minimum number of points used for full coverage is $NP$ , but it can be proven that no more than $floor rac{ n }{3} floor$ points for full coverage.
In the process of proof, the classic geometric algorithm of triangulation is used, but some details of triangulation have not been considered. For example: Can any simple polygon be triangulated? If a simple polygon has holes, can it still be triangulated?

triangulation

First define the research object. The triangulation here refers to the triangulation of simple polygons that can have holes.
A simple polygon is a polygon whose sides do not intersect, according to $Jordan$ Curve theorem, such a polygon divides the plane into an outer region and an inner region.

Rule: For a simple polygon without holes, a counterclockwise movement along the edge is the positive direction. For a simple polygon with holes, the positive direction is a counterclockwise movement along the outer boundary, and a clockwise movement along the inner hole is the positive direction.
This ensures that the interior area is on the left hand side when moving along the boundary at any time.

Two Ears theorem

Ear: For three adjacent vertices in a polygon $u,v,w$ , if the vector $verrightarrow{uv} imes verrightarrow{vw} >0$ and $riangle uvw$ does not contain any other vertices, then $u,v,w$ Three points form an ear. Intuitively, the three points satisfy local convexity and are empty inside.
For a polygon, you can cut off an ear, which will reduce the number of vertices of the polygon without changing other properties.

The two-ear theorem states that for any simple polygon, there are at least two ears.
The proof uses mathematical induction, which is omitted here. In fact, the idea of the proof is the same as the idea of the triangulation construction below.

Proof of the existence of triangulation

Use mathematical induction.
For a polygon, there are two attributes, the number of vertices $n$ and number of holes $h$ 。

Basic situation: $n=3,h=0$ , the polygon itself is a triangle, and triangulation obviously exists.
Assumption: For a vertex number of $n$ , the number of holes is $h$ of polygons. Any satisfaction: $h'<h$ or $h'=h,n'<n$ All polygons are triangulated.
In fact, this is a total order relationship, and any two polygons can be compared based on this relationship.

Consider polygons $P$ The bottom vertex $j$ (If there are multiple bottom points, take the leftmost point). There are two situations.

if $i,j,k$ is an ear, then cut it off directly, and the number of vertices is $n-1$ of polygons.
if $i,j,k$ is not the ear, then find the distance between other points of the polygon $j$ the nearest point $m$ ,connect $jm$ There are two situations for incision:

Figure 4 Triangulation

constructive proof

As shown on the left in the picture above, $m$ On the outer boundary, the polygon will break into two smaller polygons.
As shown on the right side of the figure above, $m$ Regarding holes, although the number of vertices of the new polygon increases, the number of holes decreases. Based on the total order relationship above, the new polygon is smaller in size than the original one.

According to the inductive hypothesis that triangulation exists for smaller polygons, then the polygon $P$ Triangulation also exists. End of proof.

some other properties

Uniqueness:

Not only that, the simplest convex quadrilateral has two triangulations.

The maximum number of triangulation types:

The minimum value is $1$ , the simplest concave quadrilateral has only one way of segmentation, from which other situations can be constructed.
The maximum value is reached for convex polygons.
Assume that the number of vertices of the polygon is $n$ , then the recursion formula is:
$C_n=eft egin{aligned} 1 & , & n=3 igma_{i=1}^{n-3}{C_{i+2}*C_{n-i}} & , & n>3 nd{aligned} ight.$
That is, corresponding to the $n-2$ item $Catalan$ number.

time complexity

Triangulation of polygons can be done in $O(nlogn)$ Completed within the time complexity, the following is the triangulation algorithm, which is divided into two steps: monotonic polygon decomposition and monotonic polygon inner triangulation.

Monotone Decomposition

Polygonal monotonicity

If each segment on a chain is related to a straight line $l$ The projections of only intersect at the vertices, then the polyline is opposite to the straight line $l$ Has monotonicity.

Figure 5 Polygon monotonicity

monotonic polyline

If a polygon can be divided into two complementary chains, and both chains are aligned with the straight line $l$ monotonic, then this polygon pair $l$ monotonous.

Figure 6 Monotone polyline

monotonic polygon

For convenience, in the following algorithm, the monotonic polygon refers to $y$ A polygon with monotonic axes, as shown above, is a pair of $y$ A polygon with monotonic axes.

Triangulating a monotonic polygon is quick and easy. But first the entire simple polygon must be decomposed into several monotonic polygons.
The algorithm is as follows.

Vertex type definition

For each point on the polygon, it can be divided into $5$ Classes: start vertex, end vertex, split vertex, merge vertex and regular vertex.
Assume that the current point is $q$ , whose precursor is $p$ , followed by $r$ . And for convenience, we assume that the vertical coordinates between any two points are different, although this algorithm is still correct for the case where the vertical coordinates are the same.

Starting point: if and only if $p$ and $r$ All are there $q$ below, and inside angle $ngle pqr < i$ 。
End point: if and only if $p$ and $r$ All are there $q$ above, and inside angle $ngle pqr < i$ 。
Split point: if and only if $p$ and $r$ All are there $q$ below, and inside angle $ngle pqr > i$ 。
Merge point: if and only if $p$ and $r$ All are there $q$ below, and inside angle $ngle pqr > i$ 。
Ordinary point: before you are not satisfied $4$ All grown are ordinary.

Split points and merge points are the reasons that destroy the monotonicity of polygons, so it is necessary to introduce an internal diagonal line at these two points to split the polygon into two small polygons to ensure that the two small polygons are monotonic. Obviously for the split point, we need to introduce an inner diagonal upward, and for the merge point, we need to introduce an inner diagonal downward.

Taking the split point as an example, as shown in the figure above, at the split point $v_{i}$ At , we need to find the nearest first point above the left and right borders, as shown in the figure $helper(e_j)$ , and then introduce an internal diagonal. At the same time, the original polygon will be split into two small polygons.

It should be noted that the left and right boundaries are not the closest first point above what we are looking for. $helper$ , since this point may appear in other small polygons. So we need to maintain the boundaries of multiple small polygons and be able to find and modify them.

# Art Gallery Problem

Figure 1 Art Museum Problem

# naive upper and lower bounds

# Chvátal Art Gallery Theorem

Figure 2 Art Museum Theorem

# Fisk's short proof

Figure 3 Art Museum Theorem

# triangulation

# Two Ears theorem

# Proof of the existence of triangulation