I have a delaunay triangulation for a 2d box with say an airfoil inside. If I uniformly refine this mesh by subdividing each triangle in the mesh into 4 triangles by halving each edge, is the resultant mesh still delaunay? I have been assuming so, but I have no proof this is the case.
I hope I'm not overlooking something, but it seems obvious that the mesh so refined will not be Delaunay.
EDIT: Turns out I misunderstood the procedure, and you are actually generating a fresh mesh through trimming curves/edge flips/equivalent.
Essentially you are adding vertices to the midpoints of each edge of a triangle; these midpoints lie inside the circumcircle of the original triangle. This is a violation of the Delaunay condition. You will additionally need to re-triangulate and remove some edges of the original triangle to make it Delaunay. This is not a trivial operation, and will take O(n) time.
Even so, this is not a preferred strategy for Delaunay refinement - most approaches instead add vertices at the circumcentre and proceed from there. I don't know the comparative merits of both approaches, it could be worth looking into. You may like reading this : https://www.cs.cmu.edu/~quake-papers/delaunay-refinement.pdf
Additionally, since you are halving all edges, rather than selecting which edges should be halved, you are very likely to run into problems with 'skinny triangles'. These have one edge much larger than the other, and pose a problem to Delaunay triangulation. If the edges are selectively halved, using for instance Ruppert's algorithm, then you would convert a skinny triangle into smaller, less skinny triangles.On the other hand, if you half all edges, you preserve the skinny nature of the triangle.
This is easily shown mathematically; halving each edge yields you four triangles, three sharing a vertex with the original triangle. Each of these three triangles is similar to the original triangle by the SAS criterion (one common angle between two sides sharing the same ratio. In this case the ratio will be 1:2). Thus, you are creating equally skinny triangles, and three of them. So if your original mesh had x poor-quality (i.e. skinny beyond some threshold) elements, you will now have atleast 3x poor-quality elements, which is naturally undesirable.