Timeline for Simple cake cutting puzzle
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2016 at 20:10 | comment | added | Gerhard Paseman | I think I am misunderstanding your intent, or you are not communicating it. I ask you if you can get 5 pieces under your present scheme (with all intersection points of cuts inside the circle). I maintain that you will always get 7 with three such cuts, as you are asking every two cuts to intersect uniquely on the cake. The problem I asked (given K the number of pieces, find the minimal number of cuts) is not much better or harder, but feels more like a complexity problem than this latest version. Gerhard "Perhaps I Am Missing Something" Paseman, 2016.12.12. | |
| Dec 12, 2016 at 17:36 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 4 characters in body
|
| Dec 12, 2016 at 17:27 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
deleted 41 characters in body
|
| Dec 12, 2016 at 17:20 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman Please review the edited post and give me your feedback :) | |
| Dec 12, 2016 at 17:19 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
deleted 89 characters in body
|
| Dec 12, 2016 at 17:08 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman I have a fix :). Any instance of my problem can be converted to an instance of the problem that Joseph mentioned. In other words, for any set of non-parallel cuts, enlarge the circle so that all intersection points become inside the circle. | |
| Dec 11, 2016 at 18:06 | comment | added | Gerhard Paseman | One problem that I hoped you would mention is to find the minimum number of cuts to produce K pieces. I know of no polytime (in log K) algorithm to answer that. (Actually, one just occurred to me after I hit 'send'.) Gerhard "Don't Ask For Three Pieces" Paseman, 2016.12.11. | |
| Dec 11, 2016 at 16:32 | comment | added | Gerhard Paseman | Unfortunately, that restriction does not reduce the triviality. I can take my concurrent solution and tweak the lines so that all points of intersection lie outside the circle, resulting in K pieces. To a casual observer the portion inside the circle will look unchanged. If you insist that all intersection points are strictly inside, you get what Joseph provided in his post. Tweaking a solution to allow more than two lines concurrent inside the circle allows you fewer regions. I don't think you've captured a good problem yet. Gerhard "Is Reading Between The Lines" Paseman, 2016.12.11. | |
| Dec 11, 2016 at 12:52 | answer | added | Joseph O'Rourke | timeline score: 4 | |
| Dec 11, 2016 at 12:40 | comment | added | Joseph O'Rourke | If a parallel pair's "extensions outside the circle on both ends do not cross," doesn't that imply that they are simply parallel lines clipped to the disk? | |
| Dec 11, 2016 at 8:48 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman To eliminate all trivial cases, any crossing point (inside or outside the circle) is the result of the intersection of exactly two cuts. | |
| Dec 11, 2016 at 8:47 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 163 characters in body
|
| Dec 11, 2016 at 7:26 | comment | added | Gerhard Paseman | OK. What about K-1 many concurrent lines, with common point far away from the circle, and all of them intersecting the circle non trivially (non tangentially)? Gerhard "What Does Parallel Really Mean?" Paseman, 2016.12.10. | |
| Dec 11, 2016 at 6:02 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 177 characters in body
|
| Dec 11, 2016 at 5:54 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman Crossings are NOT allowed on the circle boundary. So, two cuts either cross inside or outside the circle but they can not cross each other on the circle boundary. | |
| Dec 11, 2016 at 5:50 | comment | added | Gerhard Paseman | Assuming crossings are allowed on the circle boundary, K-1 cuts emanating from a single point do the job. Did you want general position, or a limit on the number of cuts through a point? Gerhard "Seems Too Easy To Me" Paseman, 2016.12.10. | |
| Dec 11, 2016 at 5:41 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 151 characters in body
|
| Dec 11, 2016 at 5:33 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
deleted 3 characters in body
|
| Dec 11, 2016 at 5:27 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
deleted 3 characters in body
|
| Dec 11, 2016 at 5:18 | history | asked | Mohammad Al-Turkistany | CC BY-SA 3.0 |