I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh in dimension $p$. However, this approach is asymptotically $\Omega({n}^{{p}/{2}})$. I was wondering if there are any other algorithms to produce arbitrary dimensional meshes that can be implemented faster. If so, what are they, how do they work and what is their asymptotic runtime (in terms of the number of mesh points)?

  • $\begingroup$ What is $\Omega$? What is $d$? $\endgroup$ Commented Jan 15, 2012 at 9:00
  • $\begingroup$ Using asymptotic notation (see Introduction to Algorithms 3rd Edition by Cormen et al.), it roughly means that the runtime for large problem sizes (large point sets) is at least ${n}^{p/2}$, where n is the cardinality of the point set. $\endgroup$
    – Paul
    Commented Jan 15, 2012 at 16:37
  • $\begingroup$ Thanks. But I found an explanation here that says something different: en.wikibooks.org/wiki/Data_Structures/… That says that what you wrote only means it is at least $cn^{p/2}$ where $c$ is some constant. Also, since both $n$ and $p$ are arbitrary, can you specify in which one this is asymptotic? $\endgroup$ Commented Jan 15, 2012 at 19:15
  • $\begingroup$ @DavidKetcheson The statement is only a lower bound. The asymptotic statement should be interpreted as being for any given $p$, there is $n_0$ and $c>0$ such that the algorithm takes at least $c n^{p/2}$ for all $n > n_0$. $\endgroup$
    – Jed Brown
    Commented Jan 15, 2012 at 20:00
  • $\begingroup$ @Paul Do you want a Delaunay mesh? (If the problem is anisotropic, then you would not want Delaunay.) What quality constraints? Note that Delaunay in 3D can still have quite bad elements. $\endgroup$
    – Jed Brown
    Commented Jan 15, 2012 at 20:00

1 Answer 1


How about; Watson, D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput J 24, 167–172 (1981).


If I understood it, it should be $\mathcal{O}\left(n^{\frac{2p-1}{n}}\right)$, isn't that better then $Ω\left(n^{p/2}\right)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.