  In this paper, we address the minimum-area rectangular and square annulus
problem, which asks a rectangular or square annulus of minimum area, either in
a fixed orientation or over all orientations, that encloses a set $P$ of $n$
input points in the plane. To our best knowledge, no nontrivial results on the
problem have been discussed in the literature, while its minimum-width variants
have been intensively studied. For a fixed orientation, we show reductions to
well-studied problems: the minimum-width square annulus problem and the largest
empty rectangle problem, yielding algorithms of time complexity $O(n\log^2 n)$
and $O(n\log n)$ for the rectangular and square cases, respectively. In
arbitrary orientation, we present $O(n^3)$-time algorithms for the rectangular
and square annulus problem by enumerating all maximal empty rectangles over all
orientations. The same approach is shown to apply also to the minimum-width
square annulus problem and the largest empty square problem over all
orientations, resulting in $O(n^3)$-time algorithms for both problems.
Consequently, we improve the previously best algorithm for the minimum-width
square annulus problem by a factor of logarithm, and present the first
algorithm for the largest empty square problem in arbitrary orientation. We
also consider bicriteria optimization variants, computing a minimum-width
minimum-area or minimum-area minimum-width annulus.
