3
$\begingroup$

Suppose a convex compact room in $3$-dimensions is given and source and microphones recorders are provided in the room that can locate echo timings there are works in literature which can give you the measurements of the room and from this we can get the volume.

We do not need source and receive microphones if the room is presented in form of linear inequalities. We can just compute the likely timings from the inequalities.

In this sense the computations and the timing measurements are equivalent.

Due to time-frequency duality there might be a Fourier analytic way to interpret convex polyhedra presented by linear inequalities which can lead to volume computation.

$\underline{\mbox{Motivation}}$:

I am concerned about $n$-dimensional space. Polynomial (in $n$) number of linear inequalities in $n$-dimensions suffice to get exponential (in $n$) number of vertices and faces for a convex compact room. So direct computation of distance between faces and getting volume takes exponential (in $n$) time.

$\underline{\mbox{What is known}}$:

It is unknown whether we can get exact volume of a $n$-dim convex room presented by polynomial (in $n$) number of linear inequalities in polynomial (in $n$) number of arithmetic operations.

However a randomized approximation in polynomial (in n) time (or arithmetic operations) is known.

$\underline{\mbox{What I seek}}$:

Any time-frequency duality in $3$-dim case providing fourier analytic interpretation for volume should work in $n$-dimension when the room is presented in terms of linear inequalities.

The goal is to seek whether there can be polynomial time volume approximation from a Fourier analytic theory?

Note that exact computation is likely still impossible in poly (in $n$) time. However a Fourier analytic way

  1. could provide a new way to approximate.

  2. may be deterministic (unlike the randomized schemes known).

Is there a possibility of Fourier analytic interpretation that might lead a way get volume of convex polyhedra presented by linear inequalities approximately within a constant factor in polynomial time?

Or is there a fundamental reason why any such approach cannot approximate volume better than exponential factors in polynomial time?

Improve this question
$\endgroup$
2
  • $\begingroup$ It's certainly possible to calculate the volume via Fourier analysis: $Vol(A)=\int 1_A dx$, where $1_A$ is the indicator function of $A$ equal to the product of $\Theta(\mathbf k \mathbf x -1)$ over all vectors $\mathbf k$ defining the linear inequalities. Here $\Theta$ is Heaviside's function. Since $\int 1_A dx = (\int 1_A e^{i p x} dx)|_{p=0}$ and the Fourier transform of a product is a convolution of Fourier transforms, we get a Fourier calculation for volume. The F.t. of each $\Theta$ is a sum of delta-functions on the space and on orthogonal to $\mathbf k$'s. $\endgroup$
    – Anton Fetisov
    Commented Oct 23, 2017 at 1:09
  • $\begingroup$ In principle it can be computed and gives an explicit complicated formula via all $\mathbf k$'s, but in fact it involves calculating all faces, edges, vertices etc, so it's more complex than the initial problem. It doesn't look like one could evaluate an integral of n-dimensional delta functions without computing intersections, but of course it's not a proof that some algorithm couldn't exist. $\endgroup$
    – Anton Fetisov
    Commented Oct 23, 2017 at 1:12

1 Answer 1

Reset to default
1
$\begingroup$

Check out the very nice paper by R. Diaz and S. Robins:

Diaz, Ricardo; Robins, Sinai, The Ehrhart polynomial of a lattice polytope, Ann. Math. (2) 145, No.3, 503-518 (1997); erratum ibid. 146, 237 (1997). ZBL0874.52009.

Improve this answer
$\endgroup$
1
  • $\begingroup$ neat $reference$ $\endgroup$
    – Turbo
    Commented Oct 23, 2017 at 9:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .