# Extending Delaunay graphs in d-space

I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space.

Given $n$ points in $d$-space ($d>3$), I can compute an initial Delaunay graph in $\mathcal{O}(n^{ \lfloor\frac{d}{2}\rfloor })$ time. My algorithm then operates on this graph recursively by selecting a subset of simplices, in each of which I would like to insert a single new vertex.

I do not have any preference as to where a new vertex is inserted in each selected simplex. Knowing this, I think intuitively that if I choose to insert it at the barycenter of the simplex, I can extend my Delaunay graph in constant time for each selected simplex. Is that correct?