Timeline for Partitioning a polygon into convex parts
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 13, 2022 at 11:26 | history | suggested | Adi Shavit | CC BY-SA 4.0 |
Fix Green's name to correct Greene.
|
| Jul 13, 2022 at 8:35 | review | Suggested edits | |||
| S Jul 13, 2022 at 11:26 | |||||
| Aug 23, 2020 at 18:39 | comment | added | domotorp | Oh, I see, so the answer to my question is n-2! On one hand, this is an upper bound given by any triangulation. On the other, if an n-gon has a concave arc of n-2 consecutive segments, i.e., with n-3 reflex vertices, then obviously n-2 pieces are needed. Thanks! | |
| Aug 23, 2020 at 17:34 | comment | added | Joseph O'Rourke | @domotorp: Sorry for the delay. The best possible is $\lceil r/2 \rceil + 1$, where $r$ is the number of reflex vertices, because each reflex vertex must be resolved, and at most two reflex vertices can be resolved by a single partition segment. The min might be as high as $r+1$ depending on alignment of the reflexivities. | |
| Aug 22, 2020 at 21:43 | comment | added | domotorp | (But I can wait a day.) | |
| Aug 22, 2020 at 21:43 | comment | added | domotorp | I've looked at many of these papers, but all of them seems to be about the computational complexity of the optimum value for a given input. I'm just looking for a simple expression, like n/3 for the art gallery problem. | |
| Aug 22, 2020 at 21:12 | comment | added | Joseph O'Rourke | Keil, Mark, and Jack Snoeyink. "On the time bound for convex decomposition of simple polygons." International Journal of Computational Geometry & Applications 12, no. 03 (2002): 181-192. Abstract: "We show that a decomposition of a simple polygon having $n$ vertices, $r$of which are reflex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in $O(n + r^2\min{r^2, n})$ time and space." | |
| Aug 22, 2020 at 19:50 | comment | added | domotorp | What is the minimum number of pieces needed for partitioning/covering an n-gon to convex pieces? | |
| Jul 29, 2017 at 12:47 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Broken link fixed.
|
| Mar 10, 2017 at 15:58 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Fixed image, which was temporarily lost due to StackExchange changes.
|
| Mar 31, 2011 at 18:12 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
Added figure from p.61 of book.; added 25 characters in body
|
| Mar 31, 2011 at 17:38 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |