voronoi diagrams are pretty cool tools.
since you are searching for the largest circles available and you (judging by you posting an article about voronoi diagrams) are able to use a voronoi diagram of your surface. let’s consider a few key facts about circles and voronoi diagrams.
a circle has a center equidistant from all its edges.
a voronoi diagram contains polyons where in all points are closer to a single center point than to any other.
these aren’t quite the same, but they are similar.
let’s also consider that little piece of information i was taught back in middle school. the most optimized amount of space you can get out of an area by perimeter length is a circle
while i can’t give you a proof for it, i believe we can predict a statistical tendency of larger area polygons in a voronoi diagram to also have a tendency towards larger circular inscriptions.
using this idea you can write a highly optimized algorithm to start searching the voronoi diagram for large circular inscriptions starting from the largest polygons in the diagram. i dare say you could write an algorithm not only good enough for one time calculation, but an algorithm good enough for 60fps realtime calculation every frame. mainly because voronoi is absolutely ripe for parallelization.
A truly mathematical solution may be more desired, but you asked for other solutions and i believe this is a very practical approach.
if you are looking for information on making voronoi diagrams(and finding their polygon’s area) fast, and they can be lightning fast, then i suggest this article.