# What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?

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)?

• What is $\Omega$? What is $d$? Commented Jan 15, 2012 at 9:00
• 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.
– Paul
Commented Jan 15, 2012 at 16:37
• 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? Commented Jan 15, 2012 at 19:15
• @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$. Commented Jan 15, 2012 at 20:00
• @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. Commented Jan 15, 2012 at 20:00

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)$?