Timeline for Complexity of detecting a convex body in $\mathbb{R}^n$?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2011 at 17:56 | answer | added | Michael Biro | timeline score: 3 | |
| Nov 7, 2011 at 17:52 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Nov 7, 2011 at 16:23 | history | edited | Han Xiao | CC BY-SA 3.0 |
added 18 characters in body
|
| Nov 7, 2011 at 16:07 | comment | added | Han Xiao | @Robert Israel and @Igor Rivin: Thanks for the remark. I've updated my question accordingly. | |
| Nov 7, 2011 at 16:04 | history | edited | Han Xiao | CC BY-SA 3.0 |
added 95 characters in body; edited tags; edited title
|
| Nov 7, 2011 at 1:52 | comment | added | Robert Israel | Actually that algorithm requires that the convex set has nonempty interior. | |
| Nov 6, 2011 at 22:50 | comment | added | Robert Israel | On the other hand, here's an algorithm that will eventually work if the interior of one of the sets is non-convex: take a sequence of points $x_n$ dense in $K_0$, and for each pair $i < j$ such that $x_i$ and $x_j$ are both in $K_1$ or both in $K_2$, check whether $(x_i + x_j)/2$ is there too. | |
| Nov 6, 2011 at 22:49 | comment | added | Robert Israel | It's clear that there can't be a query-based algorithm whose worst-case complexity is bounded: for any algorithm and any $n$ you can construct examples where the boundary is so close to a hyperplane that more than $n$ queries will be needed. So I don't know what Han means by "as few membership queries as possible". | |
| Nov 6, 2011 at 21:42 | comment | added | Igor Rivin | @Suvrit: there is no doubt that more information is needed for any sort of efficiency, but all the OP is asking for is AN algorithm. | |
| Nov 6, 2011 at 21:32 | comment | added | Suvrit | Can this be done? Consider for example $K_0$ is a disk; $K_1$ is some point on the boundary (or maybe a tiny arc), and $K_2$ is the rest. It seems that with high probability, a method based on queries will declare $K_2$ to be convex, and miss out on $K_1$. Or am I mistaken? | |
| Nov 6, 2011 at 20:57 | history | asked | Han Xiao | CC BY-SA 3.0 |