# 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? Commented Jan 9, 2023 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}$. Commented Jan 10, 2023 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. Commented Jan 10, 2023 at 18:32
• @nicoguaro Oh I should add that the solution set should form a polygon without any holes... Commented Jan 10, 2023 at 18:38
• I do not understand what you want to achieve. Would you mind showing us an example? Commented Jan 13, 2023 at 21:59