On computing a largest empty arbitrarily oriented rectangle

摘要

Given a set P of n points within a rectangle R, we present an O(n~3) time algorithm for computing an arbitrarily oriented empty rectangle of largest area in R that is bounded by a point of P on each of its four sides. We assume that R is large enough to contain such a rectangle.