Oriented Containers (again) - Biconvex Lenses

We add one more link to the chain of Oriented containers, the latest of which was here .
And there are two arix preprints on this topic - both done some years ago: this and this

Definition: A biconvex lens is the intersection of two circular disks - not necessarily of the same radius. It is an oriented convex region - the orientation given by the line joining the centers of the intersecting disks or its perp
endicular.

Question: To find the smallest (least area or least perimeter) biconvex lens that contains a set of n points on the plane.

A preliminary approach:
- Find convex hull of the set of n points.
- Find circles formed by 2 triplets of points on this hull and find their intersection - a biconvex lens. For each intersection check if all input points are on or within the lens. If not, reject this intersection.
- From among the lenses found in previous step that do contain all n points, pick the smallest.


The algo is polynomial but seems to have complexity O(n^7) in the worst case. Am reminded of David Mount's beautiful treatment of finding the smallest containing disk for a set of n points - a linear(!) time algo is possible there. Such a randomized incremental algorithm might be possible here as well with massive reduction in complecity.

There must be much faster algorithms!

And a constrained version of above problem - both arcs forming the lens reqd to be of equal radius - could also be interesting.

Note: Just like the biconvex lens, one can think of a crescent which is also the (concave) intersection of the interior of one disk with the exterior of another disk.

Yet another thought: Among all the oriented containers listed in all those pages and preprints - isosceles triangles, right triangles, rectangles, semicircles, ellipses, sectors, circle segments, trapezoids and now lenses - only the semicircle certainly has the property: "for any spread of points, the least perimeter container and least area container have the same orientation." (ie if "container" means semicircle"); but then, maybe the circle segment and sector too have this property. Perhaps even lenses.

And of course for every container question, there could b a containee - largest oriented convex regions that can be drawn inside convex regions!

Note added on May 28th 2023: Recall from this earlier post that most, if not all, above questions can have inside out versions. For example: Given a circle segment S, find the smallest (largest) convex region form which S is the smallest containing (largest embedded) circular segment. Smallest could be in terms of area of perimeter.