  Let $P$ be a set of $n$ points in the plane. We compute the value of
$\theta\in [0,2\pi)$ for which the rectilinear convex hull of $P$, denoted by
$\mathcal{RH}_{\theta}(P)$, has minimum (or maximum) area in optimal $O(n\log
n)$ time and $O(n)$ space, improving the previous $O(n^2)$ bound. Let
$\mathcal{O}$ be a set of $k$ lines through the origin sorted by slope and let
$\alpha_i$ be the aperture angles of the $2k$ sectors defined by every pair of
two consecutive lines. Let $\Theta_{i}=\pi-\alpha_i$ and
$\Theta=\min\{\Theta_i:i=1,\ldots,2k\}$. We further obtain: (1) Given a set
$\mathcal{O}$ such that $\Theta\ge\frac{\pi}{2}$, we provide an algorithm to
compute the $\mathcal{O}$-convex hull of $P$ in optimal $O(n\log n)$ time and
$O(n)$ space, while if $\Theta<\frac{\pi}{2}$ the complexities are
$O(\frac{n}{\Theta}\log n)$ time and $O(\frac{n}{\Theta})$ space. (2) Given a
set $\mathcal{O}$ such that $\Theta\ge\frac{\pi}{2}$, we compute and maintain
the boundary of the ${\mathcal{O}}_{\theta}$-convex hull of $P$ for $\theta\in
[0,2\pi)$ in $O(kn\log n)$ time and $O(kn)$ space, or in
$O(k\frac{n}{\Theta}\log n)$ time and $O(k\frac{n}{\Theta})$ space if
$\Theta<\frac{\pi}{2}$. (3) Finally, given a set $\mathcal{O}$ such that
$\Theta\ge\frac{\pi}{2}$, we compute the ${\mathcal{O}}_{\theta}$-convex hull
of $P$ of minimum (or maximum) area over all $\theta\in [0,2\pi)$ in $O(kn\log
n)$ time and $O(kn)$ space.
