The average distance problem involves minimizing $$\int \text{dist}^p (x,X) d\mu$$ where $X$ varies among a family of admissible sets, $p \geq 1$, and $\mu$ is a given density. Regularity of minimizers of the average distance problem is a delicate problem: it is known that Lipschitz regularity holds, while $C^1$ is false in general. For application in data analysis, the original version of the average distance problem exhibits several drawbacks, thus additional penalization terms (e.g. Willmore energy, $L^2$ norm on the density) should be considered. Moreover, due to computational cost, it is often advantageous to restrict the unknown to the family of parametrized curves. In this talk we will present some recent results on the regularity of minimizers, for both original and penalized problems. Joint work with Dejan Slepcev.