Best Fitting Rectangles
Manuel Abellanas, Ferrán Hurtado, Christian Icking, Lihong Ma, Belén Palop, Pedro A. Ramos · 2004
We solve an interesting optimization problem motivated by tolerancing metrology, paper position sensing, and facility location: What rectangle fits best a given set of points? This problem has relations to the minimum width annulus problem and also to the largest empty rectangle problem for both of which O(n log n) time solutions are not known. Nevertheless, for our problem there is a linear time algorithm for arbitrary axis-parallel rectangles and a O(n log n) solution if the aspect ratio of the rectangles is prescribed. 1