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.

  • $\begingroup$ Isn't the convex hull of your data such a polygon? $\endgroup$
    – nicoguaro
    Commented Jan 9, 2023 at 23:17
  • $\begingroup$ @nicoguaro Not really...it is possible that the convex hull that you mentioned cannot be represented by a union of triangles in $\mathcal{T}$. $\endgroup$
    – ArGenya
    Commented Jan 10, 2023 at 4:20
  • $\begingroup$ 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. $\endgroup$
    – nicoguaro
    Commented Jan 10, 2023 at 18:32
  • $\begingroup$ @nicoguaro Oh I should add that the solution set should form a polygon without any holes... $\endgroup$
    – ArGenya
    Commented Jan 10, 2023 at 18:38
  • $\begingroup$ I do not understand what you want to achieve. Would you mind showing us an example? $\endgroup$
    – nicoguaro
    Commented Jan 13, 2023 at 21:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.