This comes from a problem my coworker and I are working on, and I'm not sure whether to post it here or MathOverflow or CrossValidated or what. Please let me know if I should migrate the question.
We have a finite set of points $X$ in 2-d in convex position, and for each point $x \in X$ we want to know the defining boundary of the convex polyhedral cell of points that are FARTHER from the point $x$ than to all other $y \in X$. It turns out this is closely related to Voronoi diagrams and their dual, Delaunay triangulations. However in this case, the dual problem is given a convex polygon, to find the triangulation that MINIMIZES the MAXIMUM angle among all the angles of all the triangles in the triangulation. A more friendly version is, to find a triangulation so that for each triangle, the circle passing through the 3 vertices contains all other points in the polygon.
We've devised an edge-flipping algorithm that starts with a certain triangulation (say, random), and then quickly finds "edge flips" where flipping a crossing edge in a quadrilateral reduces the number of triangle/point pairs that violate the "all points inside the circumscribing circle" property.
The question is, what is the asymptotic (big-O) expected number of flips that have to be performed, in terms of the number of vertices $n$, assuming that the starting triangulation is chosen uniformly at random from all the triangulations?
Also, we can use a heuristic to build the initial triangulation that starts with a random edge on the convex hull and then finds the longest edge that can be added to form a triangle in the triangulation. Then it finds the longest edge that can be added to form a new triangle in the triangulation when combined with the edge previously added. In other words, it iteratively chooses between the two vertices adjacent to the currently triangulated region and chooses the new vertex that creates a new edge in the triangulation that is the longer of the two choices. Can it be shown that this helps at all, in terms of expected number of edge flips to find the optimal triangulation?