2
$\begingroup$

We continue On some optimal containers of a set of points on the 2D plane.

Let us define a biconvex lens as the intersection of two circular disks - not necessarily of the same radii. Such a figure has an 'oriented' nature - the special orientation being the line joining the two centers.

Question: Given a set of n points on the plane to find the smallest biconvex lens that contains them all. A brute-force O(n^7) algorithm can be found very easily. But what is the optimal algorithm? Is there (say) a randomized incremental algorithm on the lines given in https://www.cs.umd.edu/~mount/754/Lects/754lects.pdf (page 45)?

Note 1: In the above definition, 'Smallest' could mean smallest area or smallest perimeter - I don't have an example where the two optimizations yield different biconvex lenses.

Note 2: How constraining the two radii of the lens to be equal could impact the algorithm(s) I am not sure.

Note 3: As noted above, the biconvex lens is an 'oriented convex container' - a bunch of questions on this type of figures (some questions have been solved subsequently) were recorded at pages linked to https://nandacumar.blogspot.com/2023/04/oriented-containers-again-biconvex.html.

Improve this question
$\endgroup$
4
  • $\begingroup$ For a lens (equal radii), I count $6$ degrees-of-freedom (DOF) in the plane: $2 \times 2$ for the diameter endpoints, the common radius, and the "sector displacement": distance from the diameter $\pm$ to the circles. So not easy to pin all these DOFs down. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 12, 2023 at 19:31
  • $\begingroup$ Thank you. But can one not think of some 'perturbative' approach - say find the smallest containing circle or ellipse first and then work from there towards the smallest lens? The smallest circle can be done in linear time; not sure about the smallest ellipse but it must be much less than n^6. $\endgroup$
    – Nandakumar R
    Commented Apr 16, 2023 at 11:21
  • 1
    $\begingroup$ It is known that a minimum area ellipse must touch at least three points. An analogous result for a minimum area lens would be a step forward. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 16, 2023 at 21:25
  • $\begingroup$ Thanks again. Found that a randomized incremental algorithm does indeed work for the least area containing ellipse - github.com/dorshaviv/lowner-john-ellipse. One would guess that the same algorithm with limited changes would find the least perimeter containing ellipse as well - a further guess here is that there being no closed form for the ellipse perimeter need not prevent us from finding a least perimeter ellipse. $\endgroup$
    – Nandakumar R
    Commented Apr 17, 2023 at 16:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .