Confusion on Delaunay Triangulation and Largest inscribed circle

Question

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?

Ethelstan

Please re-read the beginning of that thread, it is about a different problem, so it is normal that the answer is not the same... You want a disk that doesn't intersect the polygon, while that thread is about finding a disk that doesn't contain any of the vertices (no mention of edges). – Chinfest

@MarcGlisse Thank you for your reply. I re-read the thread again, so the 'largest empty circle' problem doesn't consider edges? I saw that naresh mentioned he wanted to find the largest inscribed circle but since he use pointset not polygon vertices so I cannot use this algorithm then. Do you have any idea for solving this kind of problem? – Ethelstan

You should probably ask that in a new question. But first, try to understand the structure of the problem. You have n lines, and for each line you want the circle to be on a given side of that line. Can you formulate this as a linear program? – Chinfest

If the shape is given by the boundary sampled by points then this stackoverflow question gives a solution that is based on Voronoi diagrams, which are dual to Delaunay triangulations. – Indecipherable

Answer 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:

1. 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.
2. 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.

Indecipherable

Could you please clarify this statement: "You do not need to update ... but simply insert new ones..." ? For definiteness, let's take a convex polygon: {(95, -64), (100, 5), (92, 62), (-21, 79), (-53, 42,), (-62, 23), (-84, -70), (-39, -97), (-19, -98)}. Initially, 8th side collapses at T = 47.4 (unit velocity), 7th one - at T = 53.4. Step 1: remove 8th, insert new times for 7th (52.4) and 9th (116.4), step 2: remove 7th, insert new times. The value T = 53.4 is still in the priority queue, and at the top of it. So at step 3, side 7th is gonna be removed again. What am I missing? – Mulligrubs

The point is that updates make edge collapse times only smaller. So instead of update you can just insert the edge collapse with the new time and check for the duplicates later that the respective edge has been processed already. For instance, take a triangle, cut off a vertex a bit to receive a quadrilangeral. Then this short edge is processed, its neighboring edge get lower collapse times. Insert the new events. Then the old duplicates are processed you see that the edges have already been done. – Indecipherable

Answer 2

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

Deservedly