Given a set of of $N$ points $\{\mathbf x_i \in \mathcal{S}^d\}_{i = 1, \ldots, N}$, where $\mathcal{S}$ is a set of possible values, how can I find the point $\mathbf x^*$ that maximizes the minimum distance to all data points?

In other words, I want to solve:

$\max_{\mathbf x^* \in \mathcal{S}^d} \min_{i = 1, \ldots, N} (\mathbf x^* - \mathbf x_i)^2$

The distance should be the euclidian distance, but relaxation to L1 would work, too. Exhaustive search is not feasible, as $d=75$, $N = 3000$ and $|\mathcal{S}| = 4$ in my application.