4
$\begingroup$

Suppose I define the set $A \subset \mathbb{R}^3$ to be a single cell within a larger 3D Voronoi tessellation on a set of known points. $A$ is thus convex and simply-connected. Without loss of generality (for this problem at least), I take the seed point which resides within $A$ to be the origin. Let the $n$ points neighboring $A$, and which define its boundaries, be given by $\vec{x}_1, ..., \vec{x}_n$. Assume that this set of neighbors is arranged so that $A$ does not run off to infinity, i.e. it is compact. Note that the boundary of $A$ is continuous but does not have a derivative everywhere.

Define the Fourier transform $$ \hat{\chi}_A(\vec{q}) = \int d\vec{x}\, \chi_A(\vec{x})\, \mathrm{e}^{-\mathrm{i}\,\vec{q}\cdot\vec{x}}\, , $$ where $$ \chi_A(\vec{x}) = \cases{1 & $\vec{x}\in A$ \\ 0 & $\vec{x} \not\in A$ } $$ is the indicator function of $A$. What I'm looking for is some kind of simple upper bound on the magnitude of $\hat{\chi}_A(\vec{q})$, i.e. some function $f(\vec{q})$ so that $\left|\hat{\chi}_A(\vec{q})\right| \leq f(\vec{q})$. Of course, we always have that $\left|\hat{\chi}_A(\vec{q})\right|$ is less than or equal to the volume of $A$, but that's not good enough. I need something less trivial that will allow me to bound the fall off of the tail of $\left|\hat{\chi}_A(\vec{q})\right|$.

I expect (I may be wrong) that there should exist some bound of the form $$ \left|\hat{\chi}_A(\vec{q})\right| \,\leq\, \frac{c}{\left|\vec{q}\right|} \qquad\qquad (1) $$ for some $c > 0$. For example, if $A$ is a rectangular parallelpiped with sides $L_1$, $L_2$, and $L_3$, one can show that such a bound does exist, with $$ c = \frac{2 L_1 L_2 L_3}{\min_i L_i} $$ being the optimal value of $c$. If (1) is a valid form for a bound on $\left|\hat{\chi}_A(\vec{q})\right|$, then what value of $c$ (it doesn't have to be the best possible $c$) works for my Voronoi cell? If something better than (1) exists, then what is it?

There is moderate amount of literature on the Fourier transforms of indicator functions of sets, but I haven't been able to find a reference from which I can wrestle out an answer to this particular question.

Thanks very much.

$\endgroup$
4
$\begingroup$

First, I'm not an expert in any of this but I can derive a similar bound like yours but slightly more general.

Let us rotate the coordinate system such that $\vec{q}$ is pointing in the $x$-direction and let us perform the integral in $x$-direction first.

Let $L = \frac{2\pi}{|\vec{q}|}$. For any fixed $(y,z) \in \mathbb{R}^2$, let $l_{(y,z)}$ be the intersection of $A$ with the straight line passing through $(0,y,z)$ parallel to $x$-axis.

If $l_{(y,z)} \neq \emptyset$ and its length $\mu(l_{(y,z)})$ is longer than $L$, the contribution of any sub-segment whose length is a multiple of $L$ will cancel itself. In general, we can bound the integral over $l_{(y,z)}$ as:

$$\left|\int_{l_{(y,z)}} e^{-i \frac{2\pi x}{L}} dx\right| = \left|\int_0^{\mu(l_{(y,z)})} e^{-i \frac{2\pi x}{L}} dx \right| \le \left|\int_0^{\frac{L}{2}} e^{-i \frac{2\pi x}{L}} dx \right| = \frac{L}{\pi}$$

Let $P$ be the projection of $V$ onto the $yz$-plane.The integral over $A$ is bounded by:

$$\left|\int_A e^{-i\vec{q}\cdot\vec{x}} d\vec{x}\right| = \left|\int_{(y,z) \in P} \left(\int_{l_{(y,z)}} e^{-i \frac{2\pi x}{L}} dx \right) dy dz\right| \le \int_{(y,z)\in P} \frac{L}{\pi} dy dz = \frac{2 \mu(P)}{|\vec{q}|}$$ where $\mu(P)$ is the area of $P$.

This means for general $\vec{q}$, if we let $\mu(P_{\vec{q}})$ be the area of the orthogonal projection of $A$ onto a plane perpendicular to $\vec{q}$, then the integral will be bounded by

$$\left|\int_A e^{-i\vec{q}\cdot\vec{x}} d\vec{x}\right| \le \frac{2 \mu(P_{\vec{q}})}{|\vec{q}|}$$

For the special case when $A$ is a rectangular block of dimensions $L_1 \times L_2 \times L_3$, this reduces to the bound you have derived.

UPDATE

This is the worst case dependence. Let $q$ be $|\vec{q}|$. For the case of a rectangular block. If $\vec{q}$ is perpendicular to a face of $A$, the integral does falls off at a rate proportional to $\frac{1}{q}$.

If $\vec{q}$ is not perpendicular to any faces of $A$, the integral will fall off faster.

Let $P_x$ be the intersection of $A$ with a plane passing through $(x,0,0)$ parallel to the $yz$-plane. Let $f(x) = \mu(P_x)$ be its area and $[a,b]$ be the support of $f$. The integral can be rewritten as:

$$\int_{A} e^{-i\vec{q}\cdot\vec{x}} d\vec{x} = \int_a^b \left( \int_{P_x} dy dz \right) e^{-iqx} dx = \int_a^b f(x) e^{-iqx} dx\tag{*1}$$

Let $a = b_0 < b_1 < \cdots < b_n = b$ be those $x$ where $P_x$ contain a vertex of $A$. When $\vec{q}$ is not perpendicular to any faces of $A$, it is easy to verify:

  1. $f(x)$ is continuous over $[a,b]$.
  2. If $P_{b_i}$ contains an edge of $A$, $f'$ usually develop a jump at $b_i$.
  3. If $P_{b_i}$ doesn't contain any edge of $A$, $f'$ will be continuous but $f''$ usually develop a jump at $b_i$.
  4. On each $( b_{i-1}, b_i )$, $f(x)$ is a polynomial of degree at most 2.

The R.H.S of $(*1)$ can be rewritten as:

$$\begin{align}\int_a^b f(x) e^{-i qx} dx &= \sum_{i=1}^n \int_{b_{i-1}}^{b_i} f(x) e^{-iqx} dx\\ &= \frac{1}{-iq}\sum_{i=1}^n \int_{b_{i-1}}^{b_i} f(x) d e^{-iqx}\\ &= \frac{1}{-iq}\sum_{i=1}^n \left( \left[ f(x) e^{-iqx} \right]_{b_{i-1}}^{b_{i}} - \int_{b_{i-1}}^{b_i} f'(x) e^{-iqx} dx \right)\\ &= \frac{1}{-iq}\left( \left[f(x) e^{-iqx}\right]_a^b - \sum_{i=1}^n \int_{b_{i-1}}^{b_i} f'(x) e^{-iqx} dx\right)\\ &= \frac{1}{iq} \sum_{i=1}^n \int_{b_{i-1}}^{b_i} f'(x) e^{-iqx} dx\\ &= \frac{1}{q^2} \sum_{i=1}^n \int_{b_{i-1}}^{b_i} f'(x) d e^{-iqx}\\ &= \frac{1}{q^2} \sum_{i=1}^n \left( \left[ f'(x) e^{-iqx } \right]_{b_{i-1}}^{b_{i}} - \int_{b_{i-1}}^{b_i} f''(x) e^{-iqx} dx\right)\tag{*2} \end{align}$$ From this, we see the integral falls off at least at a rate $\frac{1}{q^2}$.

Furthermore, if $\vec{q}$ is not perpendicular to any edges/faces of $A$, then no $P_{b_i}$ contains any edges of $A$ and $f'$ will be continuous over $[a,b]$. The term in $(*2)$:

$$\sum_{i=1}^n \left[ f'(x) e^{-iqx } \right]_{b_{i-1}}^{b_{i}}$$

cancel itself and integrate by parts once more, one find the integral falls off even faster at a rate $\frac{1}{q^3}$.

UPDATE2

Let $\vec{x}_1, \ldots, \vec{x}_m$ be the list of vertices of $A$. For each vertex $\vec{x}_a$, let $\hat{n}_{a0}, \hat{n}_{a1}, \ldots, \hat{n}_{an_a} = \hat{n}_{a0}$ be a list of unit vectors pointing from $\vec{x}_a$ to a vertex connected to $\vec{x}_a$. The list of unit vectors are ordered in such a way when viewing from outside of $A$, they surround $\vec{x}_a$ counter-clockwisely. Let $\hat{q}$ be the unit vector in direction of $\vec{q}$. For $\vec{q}$ in general direction, the integral has following closed form expression:

$$\hat{\chi}_A(\vec{q}) = \sum_{a=1}^{m} \frac{ e^{-i\vec{q}\cdot\vec{x}_a} }{i q^3} \sum_{b=1}^{n_a} \frac{ \hat{n}_{a(b-1)} \cdot \hat{n}_{ab} \times \hat{q}}{(\hat{n}_{a(b-1)}\cdot \hat{q})(\hat{n}_{ab}\cdot\hat{q}) } $$

UPDATE3 (how to derive the formula in UPDATE2)

Let's consider the case the origin $\vec{0}$ is one of the vertex and the cell lies completely in the half space $\vec{x} \cdot \hat{q} \le 0$. Suppose the origin is connected to 3 vertices $\vec{x}_1$, $\vec{x}_2$ and $\vec{x}_3$ so that $\vec{x}_i \cdot \hat{q} < 0$ and $\vec{x}_1 \cdot ( \vec{x}_2 \times \vec{x}_3 ) > 0$. Let $\hat{n}_i = \frac{\vec{x}_i}{|\vec{x}_i|}$ be the corresponding unit vectors.

If one intersect the cell with the hyperspace $H_t = \{ \vec{x} \in \mathbb{R}^3 : \vec{x} \cdot \hat{q} \ge t \}$. The intersection will be empty when $t > 0$. When $t < 0$, the intersection is a tetrahedron with volume:

$$\mu( A \cap H_t ) = \frac{-t^3}{6}\frac{\hat{n}_1 \cdot ( \hat{n}_2 \times \hat{n}_3 )}{(\hat{n}_1\cdot -\hat{q})(\hat{n}_2\cdot -\hat{q})(\hat{n}_3\cdot -\hat{q})}$$

This implies the intersection of $A$ with the hyperplace $P_t = \{ \vec{x} \in \mathbb{R}^3 : \vec{x} \cdot \hat{q} = t \}$ is a triangle with area:

$$\begin{align} & f(t) = \mu( A \cap P_t ) = \frac{t^2}{2} \frac{\hat{n}_1 \cdot ( \hat{n}_2 \times \hat{n}_3 )}{(\hat{n}_1\cdot -\hat{q})(\hat{n}_2\cdot -\hat{q})(\hat{n}_3\cdot -\hat{q})}\\ \implies & f''(t) = \frac{\hat{n}_1 \cdot ( \hat{n}_2 \times \hat{n}_3 )}{(\hat{n}_1\cdot -\hat{q})(\hat{n}_2\cdot -\hat{q})(\hat{n}_3\cdot -\hat{q})}\tag{*3} \end{align}$$ Plug $(*3)$ into $(*2)$ and integrate will give you the contribution from this vertex.

For the more general case when $\vec{0}$ is connected to $m > 3$ vertices $\vec{x}_1, \vec{x}_2, \ldots, \vec{x}_m$ (arranged in the order as described in UPDATE2). You break the corner of $A$ at $\vec{0}$ into $m$ sub-corners:

$$( \hat{n}_2, \hat{n}_1, -\hat{q} ), ( \hat{n}_3, \hat{n}_2, -\hat{q} ), \ldots, ( \hat{n}_1, \hat{n}_m, -\hat{q} )$$

Apply the formula $(*3)$ to each sub-corner and sum over their contribution. After a little bit rearrangement, it will give you the formula in UPDATE2.

In the formula, you will notice there is a bunch of factor $\hat{n}\cdot\hat{q}$ in the denominator. When $\vec{q}$ is perpendicular to an edge or a face, one or more of them will become zero. However, if you group all the terms in the formula associated with an edge or face togather, then in the limit when these $\hat{n}\cdot\hat{q}$ become zero, their divergences cancel out and give you the $O(\frac{1}{q^2})$ and/or $O(\frac{1}{q})$ leading asymptotic behavior.

The derivation is pretty messy and I won't reproduce it here. However, for the case when $\vec{q} \perp$ to some faces of $A$, there is a much simpler derivation:

$$\int_A e^{-i\vec{q}\cdot\vec{x}} d^{3}\vec{x} = -\frac{1}{q^2} \int_A \nabla^2 e^{-i\vec{q}\cdot\vec{x}} d^{3}\vec{x} = -\frac{1}{q^2} \int_{\partial A} ( \nabla e^{-i\vec{q}\cdot\vec{x}} ) \cdot dS = \frac{i}{q} \int_{\partial A} e^{-i\vec{q}\cdot\vec{x}} \hat{q} \cdot dS $$

Split $\partial A$, the boundary of $A$, into individual faces. We immediately see that for each face $F \perp$ to $\vec{q}$, $e^{-i\vec{q}\cdot\vec{x}}$ is constant on that face and lead to a $\frac{1}{q}$ contribution proportional to the area:

$$ \frac{i}{q} e^{-i\vec{q}\cdot\vec{x}} (\pm\mu(F)) $$

(the $\pm$ sign above depends on whether $\hat{q}$ is pointing along or opposite to the outward normals of $F$).

Summary

$$\left|\hat{\chi}_A(\vec{q})\right| \sim \begin{cases} O(\frac{\sum_{F\perp\vec{q}}\mu(F)}{q}), & \vec{q} \perp \text{ some faces F of }A.\\ O(\frac{\sum_{E\perp\vec{q}}\mu(E)}{q^2}), & \vec{q} \perp \text{ some edges E but not any faces of }A.\\ O(\frac{1}{q^3}), & \text{ otherwise. } \end{cases}$$

$\endgroup$
2
  • $\begingroup$ Thank you for your excellent response! Though I didn't say so in my original post, a closed form for $\hat{\chi}_A(\vec{q})$ is very important to what I've been working on. How did you arrive at it? Was it by transforming the volume integral to an integral over the surface of $A$? I assume that for $\vec{q}$ $\perp$ to some faces there is an additional analytical $O(1/q)$ leading term, and likewise an $O(1/q^2)$ term for $\vec{q}$ $\perp$ to some edges of $A$? $\endgroup$ Apr 26 '13 at 21:29
  • $\begingroup$ @JohnBarber answer updated to include some details how to derive the formula. It is true that the integral can be expressed as a area integral over the faces. In fact, it can also be expressed as a line integral over the edges. However, I derive the answer in reverse order. I first group the contribution from vertices to contributions from edges and finally to contribution from faces... $\endgroup$ Apr 27 '13 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.