<p>Given a simple polygon (without holes), consider a given decomposition of the polygon into convex sub-polygons. Suppose there are a number <span class="math-container">$m$</span> of convex sub-polygons and the number of the vertices of the decomposed grid is <span class="math-container">$v$</span>.</p>
<p>I am looking for the complexity of <span class="math-container">$v$</span> in <span class="math-container">$m$</span>.</p>

CC BY-SA 4.0
2022-07-09T09:17:55.160Z
Rather than "the complexity", do you mean "the relationship between $v$ and $m$?

You should state that you are looking for the decomposition into a minimal number of convex subcomponents, because any polygon of $v$ vertices can be decomposed into $\lceil v/3 \rceil$ convex components...

People might be more inclined to answer if you mention the context in which such question arise (e.g. if it was a homework assignment, you are supposed to find out by yourself, not asking the community to solve it for you, while if it is for a research question, you should be able to give its general context)
J.y B.y
CC BY-SA 4.0
2022-07-10T14:30:43.013Z
Thank you, for your comment. I mean complexity. For example, we know that the intersection of n lines is in O(n^2) so we can conclude that m is in O(v^2). However, I think we can improve this bound to O(v log v). If it is not proven yet. Note that a simple polygon can be decomposed to any number of convex polygons as we want. Also, note that v is the number of the vertices of the grid, not the polygon.
Arash Vaezi
CC BY-SA 4.0
2022-07-11T09:26:37.880Z
Oh! I think that your question would benefit from 1) some concrete examples and 2) showing "your work", for instance some examples of partial results you want to improve upon.
J.y B.y
<computational-geometry>
Complexity of the vertices of a decomposed simple polygon to its cells
Arash Vaezi
# Complexity of the vertices of a decomposed simple polygon to its cells

(Asked by: username_0 on 2022-07-06)

Given a simple polygon (without holes), consider a given decomposition of the polygon into convex sub-polygons. Suppose there are a number $m$ of convex sub-polygons and the number of the vertices of the decomposed grid is $v$.

I am looking for the complexity of $v$ in $m$.

**Tags:** computational-geometry

> **Comments:**
> **username_1**: Rather than "the complexity", do you mean "the relationship between $v$ and $m$?  You should state that you are looking for the decomposition into a minimal number of convex subcomponents, because any polygon of $v$ vertices can be decomposed into $\lceil v/3 \rceil$ convex components...  People might be more inclined to answer if you mention the context in which such question arise (e.g. if it was a homework assignment, you are supposed to find out by yourself, not asking the community to solve it for you, while if it is for a research question, you should be able to give its general context)  
> **username_0**: Thank you, for your comment. I mean complexity. For example, we know that the intersection of n lines is in O(n^2) so we can conclude that m is in O(v^2). However, I think we can improve this bound to O(v log v). If it is not proven yet. Note that a simple polygon can be decomposed to any number of convex polygons as we want. Also, note that v is the number of the vertices of the grid, not the polygon.  
> **username_1**: Oh! I think that your question would benefit from 1) some concrete examples and 2) showing "your work", for instance some examples of partial results you want to improve upon.  

---

## 0 answers

