I am reading the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al. Chapter 3 Polygon Triangulation has the following exercise 3.6:
Give an algorithm that computes in $O(n \log n)$ time a diagonal that splits a simple polygon with n vertices into two simple polygons each with at most $\lfloor2n/3\rfloor + 2$ vertices. Hint: Use the dual graph of a triangulation.
So, I have established that the dual graph (which is a graph whose nodes correspond to triangles of the triangulation and whose edges connect the nodes which correspond to triangles that share a segment):
- Is a tree.
- Each node has 0 to 3 children.
So, my current idea is a) pick some node as the root of the tree and b) use dfs to calculate the weights of all nodes. By weight of a node I mean the number of nodes in the subtree. So, for example, the weight of the root node is the total number of nodes in the tree and the weight of each leaf is 1. Then, I can perform a search for a split node that would have a weight between $\lfloor n/3\rfloor + 1$ and $\lfloor 2n / 3\rfloor + 2$.
However, I am having a hard time understanding if such a node would exist. Could you help me out?