Timeline for Complexity of detecting a convex body in $\mathbb{R}^n$?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2011 at 18:55 | comment | added | Joel David Hamkins | But we could resurrect the left/right side argument by allowing that as a legitimate input, for if we allow both $K_1$ and $K_2$ to be convex, it seems we should allow the boundary in such cases to be a plane. (I also argued this way in the second theorem of my answer.) | |
| Nov 7, 2011 at 18:37 | comment | added | Joel David Hamkins | The point is that it isn't a problem for it not to halt in a finite number of steps in that instance, since it wasn't a legitimate input. I've realized that the left/right solution I've proposed also doesn't fix the issue, since in the left/right division, the boundary is a plane, which isn't allowed. So again there is no guarantee that the main algorithm will halt in that case, and so we never get the finite list of queries. | |
| Nov 7, 2011 at 18:34 | comment | added | Michael Biro | I don't understand why that objection is a problem. I've shown that for any finite number of queries, there exists a $K_2$ with nonempty interior for which none of the query points reports $K_2$. If the algorithm needs to find points in $K_2$ to do something interesting, I can keep playing hide-and-seek with $K_2$, for any finite number of queries. So, either the algorithm halts and gives an incorrect answer, or it doesn't halt in a finite number of steps. | |
| Nov 7, 2011 at 18:27 | comment | added | Joel David Hamkins | But it seems that you can do this also. Instead of letting $K_1$ always say yes, just let it do so for points on the left side of the sphere, and otherwise $K_0$ on the right side. Now you get your query points, and then shrink to the convex hull on one side or the other, so as to change the answer. | |
| Nov 7, 2011 at 18:24 | comment | added | Joel David Hamkins | That is, what you need to do is start from an actual legal instance, let the algorithm halt with its answer, and then produce a modified version answering the queries in the same way, but having a different answer. (And this is how I argue in my answer.) | |
| Nov 7, 2011 at 18:15 | comment | added | Joel David Hamkins | Your proof doesn't quite work, since the algorithm that always says points are in $K_1$ might actually never halt. You cannot guarrantee that it does halt, since the hypotheses on the sets required that $K_2$ has nonempty interior, and perhaps the algorithm only starts doing something interesting once it has found lots of points in both $K_1$ and $K_2$. | |
| Nov 7, 2011 at 17:56 | history | answered | Michael Biro | CC BY-SA 3.0 |