  We describe a randomized algorithm that, given a set $P$ of points in the
plane, computes the best location to insert a new point $p$, such that the
Delaunay triangulation of $P\cup\{p\}$ has the largest possible minimum angle.
The expected running time of our algorithm is at most cubic, improving the
roughly quartic time of the best previously known algorithm. It slows down to
slightly super-cubic if we also specify a set of non-crossing segments with
endpoints in $P$ and insist that the triangulation respect these segments,
i.e., is the constrained Delaunay triangulation of the points and segments.
