10
$\begingroup$

Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is convenient to think of each of these points as lying in $\mathbb{C}$, and so a polygonal curve with n vertices can be thought of as a point in $\mathbb{C}^n$.

Now consider the discrete Fourier transform of this polygon:

\begin{equation} X_k = \sum_{j=0}^{n-1}x_j \cdot e^{-2\pi ijk/n}, k \in \mathbb{Z}. \end{equation}

Is it possible to determine directly from these Fourier coefficients $X_k$ whether our original polygonal curve is convex or not? or whether it is simple (non-self-intersecting) or not?

[Three short comments added in edit]

  1. The same question can also be asked for smooth curves and their Fourier transforms; perhaps more is known in that case.
  2. Changing the first Fourier coefficient $X_0$ only translates the curve, so does not affect convexity or simplicity.
  3. There is some ambiguity in defining convexity (for curves) that is relevant to this question. In particular, if $X_k = 0$ for all but one $k \neq 1$ that divides $n$, then the curve is a $k$-cover of the regular $n/k$-gon. It is not clear whether such curves should be considered convex or not.
Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – MERTON
    Commented Mar 20, 2016 at 4:38
  • $\begingroup$ 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. $\endgroup$
    – Menachem
    Commented Mar 21, 2016 at 0:11
  • $\begingroup$ 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. $\endgroup$
    – MERTON
    Commented Mar 21, 2016 at 0:44
  • $\begingroup$ 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. $\endgroup$
    – Menachem
    Commented Mar 21, 2016 at 1:40
  • $\begingroup$ 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)$. $\endgroup$
    – MERTON
    Commented Mar 21, 2016 at 3:19

0

Reset to default

You must log in to answer this question.