Inscribing two circles in convex polygon, with max sum of radiuses

Question

I'm trying to solve problem "Inscribing two circles in convex polygon, with max sum of radiuses". I can inscribe one circle in convex polygon with max radius, but what about two circles? Is there any algorithms that solves my problem.

Analytical algorithms are preferable to numerical ones.

Answer 1

The only thing that I can think of that could work within the constraints is to divide and conquer the problem:

1. iterate "all" possible cuts of your shape into two by simple line

   I would use greedy 2x nested search like approximation search as heuristics so the brute force will turn into much better complexity of O(log^2(n)) where n = shape_circumference/accuracy.

   So simply nest 2 for loops/searches that go along the whole circumference and cut the shape by the line they form. To boost speed you can add another heuristics like:

   No need to test the same 2 points in reverse order so the other for loop can start from the first point.

   No need to test full circumference for the second for loop as the correct answer will be most likely as close to perpendicular to circumference at both points as its possible so you can search only angles near by with some margin of error for example +/-30 degrees

2. compute inscribed circle for both shapes sharing the same point along the cut line

   this can be another search so adding another O(n) or O(n^2) resulting in O(log(n)^3) or O(log(n)^4) which is not that bad.

   I see it like this:

   

   And the correct point will be most likely near center "slightly" offset by the ratio between angle between cut line and "average" circumference angle on both sides of cut line

   

However this is just my intuition that such result will be the "best" and not just some greedy result in almost the best with possibility of missing correct answers! Geometric/Math proofs are not my thing.

On top of all this the cut line will be most likely close to perpendicular to shape major axis (longest center line if exist) so computing OBB or PCA or the biggest center line directly could speed up the points search and also the cut line position will be offset from shapes center by the "average" perpendicular width to the center line of the cuts which can be used to speed up the search again ...

width (brown) ratios offset (orange) the cut line from center:

You can also search the biggest center line with O(log(n)^2) search similarly to the cut line search if you do not want to implement OBB,PCA...