Largest Semidisk inside a Convex Polygon

The preprint https://arxiv.org/abs/2005.10245 had addressed the question of finding the smallest semicircular region (semidisk) that contains a given set of points - basically that contains the convex hull of the set of points. Here, we ponder another question: find the largest semicircle inscribed in a convex polygon.

Here is an attempt to sketch an algorithm for an N vertex convex P.

Observation: The largest semicircle inside a convex polygon P necessarily has both end points of its diameter on the boundary of P.

We need to consider two classes of semicircles as candidates.
(1) Semicircles with both end points on different edges of P
(2) Semicircles with both end points on the same edge of P:

Note: Here, we discuss only case 1. Case 2 can be done with slight modifications to what we show.

For each pair of edges {E1, E2} of P (let their lengths d1 and d2), we do the following:
============================
Every chord of P from somewhere on E1 and ending somewhere on E2 is a candidate for the diameter for the largest inscribed semicircle – obviously, the midpoint of this chord has to be center and half the length of the chord, the radius of a candidate semicircle. Let us parametrize the edges E1 and E2 with α and β - distances measured along them from one end point to the other. To every (α, β) pair corresponds a candidate diameter chord of P and 2 semicircles with this as diameter – the two lie on either side of the candidate diameter. For each point (α, β) that lies in a rectangle on the α- β plane, we can easily find the value of corresponding semicircle radius as a continuous function of α and β. First we plot these radii as a curved surface above (α, β) as R(α, β).

Now, we calculate how these semicircles for edge pair {E1, E2} are interfered with by edges (O(N)in number) of P - including E1 and E2. Here is how we process one such edge E:

For each α and β, apart from R(α, β), we also have the semicircle center whose coordinates are also functions of α and β. So, for a given edge E, we can find minimum distance from E to this center(α, β) as a continuous function of α and β; call this d(E, α, β) and it forms another surface above the α-β plane.

Evidently, at any point above (α, β), if d(E, α, β) < R(α, β), that (α, β) chord of the polygon is disallowed by edge E – in other words, viewed upwards from the (α, β) plane, at least a portion of the R(α, β) surface has now become ‘screened’ by the d(E, α, β) surface.

So, for every edge E of P including E1 and E2, we plot d(E, α, β) above (α, β), and from the portion of the plot of R(α, β) that is still ‘visible’ from the (α, β) plane (ie. left unscreened by all the d surfaces), pick the highest point and this gives, for the edge pair {E1, E2}, the highest radius semicircle that can be drawn with diameter end points on E1 and E2.
============================
The above processing for each edge pair {E1, E2} appears to be O(N^2) in complexity – we need to compute intersections of O(N) d surfaces sequentially with the R-surface and with each intersection, the complexity of the remaining part of the R- surface could increase to O(N).

So, since there are O(N^2) pairs of edges, we roughly estimate the overall complexity of the algorithm as O(N^4).

Of course, there are some ‘filters’ which eliminate a lot of the processing. For example:

For each candidate diameter, at its end points the edges E1 and E2 necessarily either (1) converge to one side of the candidate edge and diverge towards the other side (2) are parallel. On the side towards which E1 and E2 converge, no semicircle is possible; they are all ruled out. See the picture below:

For any chord joining the given E1 and E2, only the candidate semicircle and other edges of P on the left side of the chord need to be considered because E1 and E2 together converge towards the right.

However, this filter does not seem to reduce the complexity from O(N^4).

Further Questions (10th December 2020): Just as the semidisk, one can ask for  algorithms to find the largest circular segment (two cases, the segment with most area and the one with most perimeter) and largest sector (again, area and perimeter cases) that can be inscribed in a given convex (and further, general) polygon.