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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.