Confusion on Delaunay Triangulation and Largest in

I need to find a largest inscribed circle of a convex polygon, I've searched many sites and I get that this can be done by using Delaunay triangulation. I found a thread in CGAL discussion with an algorithm using CGAL:

You can compute this easily with CGAL:

First, compute the Delaunay triangulation of the points.

Then, iterate on all the finite faces of the triangulation. For each finite face f

compute its circumcenter c

locate c in the triangulation (to speed up things, you can give one vertex of f as starting hint for the point location)

if the face returned by locate(c,hint) is finite, then the circumcenter c lies in the convex hull of the points, so, f is a candidate

if f is such a candidate face, compute its squared circumradius keep only the face with minimum squared circumradius

The CGAL manual (chapter 2D triangulation, together with a few things from the kernel) shows every basic function to do this.

I was a bit confused with the last part of this algorithm. When I read it what I understand from it is that the minimum circumradius of the triangulation face is the radius for the largest inscibed circle. But from examples of polygon with Delaunay triangulation, it seems that even the smallest circumcircle sometimes cannot fit inside the polygon, so how can this has the same radius as the largest inscribed circle?

回答1:

Maximum inscribed circle in polygons. The classical computational-geometry solution to the maximum inscribed circle problem for polygons is to use the generalized Voronoi diagram of the polygon's faces resp. the medial axis of the polygon. This approach works in a more general setting like polygons with holes, see this stackoverflow answer to a similar question.

Convex input. The convexity of your input polygon, however, gives the problem more structure, which I would like to comment on. Consider the following convex input polygon (black), the Voronoi diagram (blue), and the maximum inscribed circle (green) centered on a Voronoi node.

The classical Voronoi-based solution is to (i) compute the Voronoi diagram and (ii) take the Voronoi node with largest clearance (i.e., distance to its defining faces).

The Voronoi diagram of a polygon with holes (i.e., the set of vertices and edges) can be computed in O(n log n) time, c.f. Fortune's algorithm (1986). Later Chin et alii (1999) gave an O(n) algorithm for the medial axis of a simple polygon.

For convex polygons, however, a time-optimal algorithm for Voronoi diagram that runs in O(n) time was already known in 1989 due to Aggarwal et alii. This algorithm follows basically the following idea: Consider the grey offset curves moving inwards at unit speed. If you project this movement into three-space where the z-axis is time you get a unit-slop roof over the polygon:

This roof model could also be characterized as follows: Put a half-space on each polygon edge at 45° slope with polygon (such that they contain the polygon) and intersect them all. So if you can quickly compute the intersect of half-spaces then you can also quickly compute Voronoi diagrams of convex polygons. Actually, for the maximum inscribed circle problem we do not need to go back to the Voronoi diagram but take the one peak of the roof, which marks the center of the maximum inscribed circle.

Now the half-spaces are dualized to points, and then the intersection of half-spaces corresponds the convex hull of its dual points. Aggarwal et al. now found an O(n) algorithm for the convex hull of points that stem from this setting.

A summary of this construction that leads to a Voronoi diagram algorithm for convex polyhedra in any dimension can be found in a blog article of mine.

Simple & fast implementation. A simpler algorithm to compute the Voronoi diagram is motivated by straight skeletons. For convex polygons the Voronoi diagram and the straight skeleton are the same.

The algorithm behind the straight-skeleton implementation Stalgo basically simulates the evolution of the wavefront structure (the grey offset curves). For convex polygons this reduces to finding the sequence of edges that collapse.

So a simple O(n log n) algorithm could look like this:

Construct a circular list of the polygon edges. Compute the collapse time of each edge during wavefront propagation, and insert this event into a priority queue.
Until the queue is empty: Take out the next edge-collapse event: Remove the edge from the circular structure and update the collapse times of the neighboring edges of the removed edge.

Actually, you can simplify the above algorithm further: You do not need to update edge collapses in the priority queue but simply insert new ones: Since the new collapse time of edges are strictly lower, you always get the right event first and dismiss the others and the queue is not growing larger than 2n. Hence, you do not compromise the O(n log n) time complexity.

For the maximum inscribed circle problem you can simplify the above algorithm even further: The Voronoi node (resp. straight skeleton node) you look for is due to the collapse of the final triangle at the end of the loop over the priority queue.

This algorithm should be quick in practice and only a few lines of code.

回答2:

The last step can mean to select the minimum face of the triangle. Then rinse and repeat.