Timeline for Determining convexity of a polygon from its Fourier coefficients
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 21, 2016 at 3:19 | comment | added | MERTON | Okay, now I understand your question. However I think it may be better to state this question in terms of algorithms and runtimes. "Computing directly" is a bit too vague to convey the intended meaning, and I don't think it means anything formally. Btw, Fourier transform takes $O(n\log n)$ time. So the question is, given $n$ complex numbers $X_0,\ldots,X_{n-1}$ is there an algorithm to detect if $x_0,\ldots,x_{n-1}$ forms a convex polygon in the complex plane in time better than $O(n\log n)$. | |
| Mar 21, 2016 at 1:40 | comment | added | Menachem | Perhaps the question can be more more precise by noting that determining convexity from the polygon vertices can be done in time $O(n)$, whereas computing the inverse Fourier transform of $X_k$ requires time $O(n^2)$. We can then ask -- can we determine convexity from $X_k$ in time $O(n)$? Really I want a "direct" method, but perhaps this reformulation makes it more concrete. | |
| Mar 21, 2016 at 0:44 | comment | added | MERTON | If you want the necessary and sufficient conditions then it is very simple to derive (but I doubt if it is useful): that the inverse Fourier transform of $X_0,\ldots,X_{n-1}$ forms a polygon. I don't see a reason why one should be able to find a criterion that is equivalent to this but formally simpler than this. | |
| Mar 21, 2016 at 0:11 | comment | added | Menachem | Right -- of course we can invert the transform to obtain the positions of the polygon vertices, and then use a traditional algorithm to determine convexity (or simplicity). My question is whether there is some way of "looking directly" at the Fourier coefficients and determine this. I am interested in both necessary and sufficient conditions. | |
| Mar 20, 2016 at 4:38 | comment | added | MERTON | The answer to the question "is it possible" should be yes, since this is an invertible transform. I am assuming you are asking for simple criteria on $X_0,\ldots,X_{n-1}$ that are either 1- Sufficient to say that $x_0,\ldots,x_{n-1}$ forms a convex polygon 2- Necessary to say $x_0,\ldots,x_{n-1}$ is a convex polygon. Can you elaborate on that? | |
| Mar 20, 2016 at 4:30 | history | edited | Menachem | CC BY-SA 3.0 |
added three short comments
|
| Mar 18, 2016 at 5:16 | history | asked | Menachem | CC BY-SA 3.0 |