Largest unit rectangles inscribed in a convex polygon (Q6639378)

The authors investigate the problem of finding the largest unit rectangle that can be inscribed within a convex polygon, specifically a convex \( n \)-gon. They present two distinct algorithms for this purpose:\N\begin{itemize}\N\item[1.] An \( O(n \log n + U) \)-time algorithm, where \( U \) represents the total number of intersections between unit circles centered at the vertices and the edges of the polygon. This algorithm achieves a time complexity of \( O(n^2) \) in the worst case when \( U = \mathcal{O}(n^2) \), but performs near-linearly in most practical scenarios.\N\item[2.] An output-sensitive algorithm that runs in \( O(n \log n + n/h) \) time, where \( h \) is the height of the largest rectangle, which allows for more efficient execution when the height is known.\N\end{itemize}\NThe paper also emphasizes the practical relevance of this problem in real-world scenarios, such as industrial applications involving spray guns with strip nozzles, scan path planning for defect inspection, and others. Finally, the authors raise two open questions about the combinatorial structures of inscribed unit rectangles, which stimulate further investigation into the problem.\N\NThe topics of the paper are interesting. The manuscript presents a well-written, theoretically robust, and practically relevant solution to a geometric optimization problem that has significant real-world applications. The authors' algorithms provide an efficient approach to solving the problem, and the paper is well-structured, making it accessible for readers in computational geometry and related fields.