  The increasing volume of data streams poses significant computational
challenges for detecting changepoints online. Likelihood-based methods are
effective, but a naive sequential implementation becomes impractical online due
to high computational costs. We develop an online algorithm that exactly
calculates the likelihood ratio test for a single changepoint in
$p$-dimensional data streams by leveraging fascinating connections with
computational geometry. This connection straightforwardly allows us to recover
sparse likelihood ratio statistics exactly: that is assuming only a subset of
the dimensions are changing. Our algorithm is straightforward, fast, and
apparently quasi-linear. A dyadic variant of our algorithm is provably
quasi-linear, being $\mathcal{O}(n\log(n)^{p+1})$ for $n$ data points and $p$
less than $3$, but slower in practice. These algorithms are computationally
impractical when $p$ is larger than $5$, and we provide an approximate
algorithm suitable for such $p$ which is $\mathcal{O}(np\log(n)^{\tilde{p}+1}),
$ for some user-specified $\tilde{p} \leq 5.$ We derive some statistical
guarantees for the proposed procedures in the Gaussian case, and confirm the
good computational and statistical performance, and usefulness, of the
algorithms on both empirical data and on NBA data.
