  We consider $L^1$-TV regularization of univariate signals with values on the
real line or on the unit circle. While the real data space leads to a convex
optimization problem, the problem is non-convex for circle-valued data. In this
paper, we derive exact algorithms for both data spaces. A key ingredient is the
reduction of the infinite search spaces to a finite set of configurations,
which can be scanned by the Viterbi algorithm. To reduce the computational
complexity of the involved tabulations, we extend the technique of distance
transforms to non-uniform grids and to the circular data space. In total, the
proposed algorithms have complexity $\mathscr{O}(KN)$ where $N$ is the length
of the signal and $K$ is the number of different values in the data set. In
particular, the complexity is $\mathscr{O}(N)$ for quantized data. It is the
first exact algorithm for TV regularization with circle-valued data, and it is
competitive with the state-of-the-art methods for scalar data, assuming that
the latter are quantized.
