This question arises from an application to graphical models in probability theory, but I have abstracted that part out so only algebra remains. Let $\mathbb{R}$ denote standard field of real numbers and $\mathcal{R} = (\mathbb{R}\cup\{\infty\},\min,+)$ the tropical semiring. Let $\mathbb{Z}\_n$ denote the cyclic group of order $n$.


Elements of the group ring $\mathbb{R}\mathbb{Z}\_n$ are tuples $(x\_0,\ldots,x\_{n-1})$ and multiplication of these corresponds to discrete cyclic convolution. The Fast Fourier Transform gives an embedding $\mathbb{R}\mathbb{Z}\_n\to\mathbb{C}^n$ (with elementwise sum and product). The FFT and its inverse can be computed in $O(n\log n)$ arithmetic operations, so elements of $\mathbb{R}\mathbb{Z}\_n$ can be multiplied in $O(n\log n)$ arithmetic operations.


Define the group semiring $\mathcal{R}\mathbb{Z}\_n$ in an analogous way. The product of $x = (x\_0,\ldots, x\_{n-1})$ and $y = (y\_0,\ldots,y\_{n-1})$ in this semiring is given by $(x\cdot y)\_k = \min \_{j \in \mathbb{Z}\_n} (x\_j + y\_{k-j})$. This operation could perhaps be called "discrete cyclic infimal convolution" by analogy with [the notion of infimal convolution in convex analysis](http://en.wikipedia.org/wiki/Convex_conjugate#Infimal_convolution). I'm not sure whether there is a more standard name -- this one does not pop up in quick google searches.


The naive way of computing a discrete infimal convolution uses $O(n^2)$ operations, just as the naive method for computing a standard cyclic convolution. **My question is: is there a way to compute this "discrete cyclic infimal convolution" in $O(n\log n)$ arithmetic operations?**


In convex analysis, there is an analog of the Fourier transform which turns infimal convolution into pointwise addition: the [convex conjugate (or Fenchel or Legendre transformation)](http://en.wikipedia.org/wiki/Convex_conjugate). However, this operation only behaves nicely for convex functions, so it is not clear to me how one would translate it to an equivalent tool for $\mathcal{R}\mathbb{Z}\_n$, but perhaps there is something there.


I would be interested in answers to the question regardless of whether they go through some analog of the Fourier transform. Also, I don't mind various restrictions such as making $n$ a power of $2$, replacing $\mathbb{R}$ with $\mathbb{Q}$, removing $\infty$ from the definition of the semiring, etc. Really anything on this theme would be helpful. Also any suggestions for better tags would be appreciated; perhaps this is a well-studied area I'm not aware of.



Efficient computation of "discrete infimal convolution"
After a bit more google searching, I found the 2006 paper [Necklaces, Convolutions, and X+Y](http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/necklace.pdf), which addresses this problem. The nine authors give an $O(n\sqrt{n})$ algorithm in the nonuniform linear decision tree model (I'm having little trouble pinning down the details of this computational model) and an $O\left(\frac{n^3(\log \log n)^3}{(\log n)^2}\right)$ algorithm in the real RAM model. I haven't found any newer results, so it seems that the problem I posed is open.


