Largest Subsets of Triangles in a Triangulation
Boris S. Aronov, Marc J. van Kreveld, Maarten Löffler, Rodrigo I. Silveira · 2007
Given a triangulation of n points, with some triangles marked “good”, this paper discusses the problems of computing the largest-area connected set of good triangles that (i) is convex, (ii) is monotone, (iii) has a bounded total angular change, or (iv) has a bounded negative turning angle. The first, second, and fourth problems are solved in polynomial time, the third problem is NP-hard. 1