
The author gives an optimal linear time algorithm for triangulating on \(n\)-vertex simple polygon, thus a longstanding and basic open problem is settled. The underlying quite clear and intuitive ideas rely on the balanced divide and conquer, polygon cutting theorem and the plane separator theorem. However the full understanding of all details is a non-trivial task. In my opinion the step by step implementation is almost impossible in the present state of the algorithm.
510.mathematics, Analysis of algorithms and problem complexity, Computer graphics; computational geometry (digital and algorithmic aspects), simple polygon, triangulation, Article
510.mathematics, Analysis of algorithms and problem complexity, Computer graphics; computational geometry (digital and algorithmic aspects), simple polygon, triangulation, Article
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 496 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 0.1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 1% |
