# Maximal "Convex Augmentation" of a Triangle in 2D Mesh

Consider a convex polygon in $$\mathbb{R}^2$$ with multiple convex holes in it and suppose that, for now, we have a 2D triangular mesh of the polygon, which is represented by $$\mathcal{T} \equiv\{T_i\}_i$$, a set of triangles in $$\mathbb{R}^2$$. My question is, given a triangle $$T$$ that lies at the exterior boundary of the polygon, is there a way to find a set $$\{T_{i_j}\}_j \subset \mathcal{T}$$ such that

$$\left(\bigcup_j T_{i_j}\right)\cup T$$

forms the largest convex polygon (without any holes) that contains $$T$$? Any help or hint will be greatly appreciated!

My Attempts:

I first wanted to solve the problem with a greedy algorithm. That is, check whether the union between $$T$$ and (not necessarily all) other triangles that share edges with $$T$$ is convex. If so, combine them and repeat this step with the resulting shape, and terminate when no more such triangles can be merged. But I find it hard to guarantee that the final resulting shape will be maximal.

• Isn't the convex hull of your data such a polygon? Jan 9 at 23:17
• @nicoguaro Not really...it is possible that the convex hull that you mentioned cannot be represented by a union of triangles in $\mathcal{T}$. Jan 10 at 4:20
• But if you have holes in your mesh then the convex set that you are looking for should be formed by triangles outside your initial set. Jan 10 at 18:32
• @nicoguaro Oh I should add that the solution set should form a polygon without any holes... Jan 10 at 18:38
• I do not understand what you want to achieve. Would you mind showing us an example? Jan 13 at 21:59