Computer Science

# Grids

How many different possible triangulations can be constructed for a regular hexagon?

How many triangles will the triangulation of a simple polygon with $51$ sides contain?

Suppose a convex polygon has vertices $v_{0}, \ldots, v_{n}$. In any triangulation we can assign a weight to each triangle to be the length of its perimeter. Let the cost of a triangulation be the sum of the weights of its component triangles. Write an algorithm to find a triangulation with the minimum cost.

If $A$ the minimum cost of triangulation for a convex polygon with the the coordinates below, what is the value of $\left\lfloor A \right\rfloor$?

$(-2,3), (4,0), (8,7), (5,10), (1,10)$

×