Return to Question

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related - the largest area circular segment inside a convex region might even be the one determined by the longest circular arc that can be drawn within the region.

Further thought: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P. I am not sure if there is a convex region that contains an arc of an ellipse longer than the max perimeter full ellipse it contains.

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related.

Further thought: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P. I am not sure if there is a convex region that contains an arc of an ellipse longer than the max perimeter full ellipse it contains.

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related.

Further thought: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P. I am not sure if there is a convex region that contains an arc of an ellipse longer than the max perimeter full ellipse it contains.

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related - the largest area circular segment inside a convex region might even be the one determined by the longest circular arc that can be drawn within the region.

Further thought: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P. I am not sure if there is a convex region that contains an arc of an ellipse longer than the max perimeter full ellipse it contains.

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related.

Further question: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P.

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P. For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.

An O(n) algorithm where n is the number of vertices of P would be nice - indeed, an O(n) algorithm is well-known for finding the longest line segment contained in P (its diameter). I don't know if (say) the longest arc that can lie in P (if not a full circle) has at least one of its end points as a vertex of P.

Note: This doc: https://arxiv.org/ftp/arxiv/papers/2005/2005.10245.pdf attempts to find the smallest circular segment containing a given convex polygon. Turning the question inside out (in the spirit of say, https://nandacumar.blogspot.com/2021/03/more-on-oriented-containers-and.html), gives the question of finding the largest area circular segment contained inside the convex polygon. The present question appears closely related.

Further thought: Although we don't have a closed formula for the perimeter of an ellipse, it might be meaningful to ask for the longest arc of an ellipse contained in a given P. I am not sure if there is a convex region that contains an arc of an ellipse longer than the max perimeter full ellipse it contains.