Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

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{R}\mathcal{H}}_{\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 sizes of the $2k$ angles defined by pairs of two consecutive lines, $i=1, \ldots , 2k$\mathrm{.}Let$\Theta_{i}=\pi-\alpha_i$and$\Theta=\min{\Theta_i \colon i=1,\ldots,2k}$\mathrm{.}Weobtain:(1)Givenaset$$\mathcal{O}$$suchthat$\Theta\ge\frac{\pi}{2}$,weprovideanalgorithmtocomputethe$$\mathcal{O}$$-convexhullof$P$inoptimal$O(n\log n)$timeand$O(n)$ space; If $\mathrm{\Theta }<\frac{\pi }{2}$, the time and space complexities are $O(\frac{n}{\mathrm{\Theta }}\log n)$ and $O(\frac{n}{\mathrm{\Theta }})$ respectively. (2) Given a set $\mathcal{O}$ such that $\mathrm{\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)$timeand$O(kn)$space,orif$\Theta < \frac{\pi}{2}$,in$O(k\frac{n}{\Theta}\log n)$timeand$O(k\frac{n}{\Theta})$space\mathrm{.}(3)Finally,givenaset$$\mathcal{O}$$suchthat$\Theta\ge\frac{\pi}{2}$,wecompute,in$O(kn\log n)$timeand$O(kn)$ space, the angle $\theta \in [0,2\pi )$ such that the ${\mathcal{O}}_{\theta }$-convex hull of $P$ has minimum (or maximum) area over all $\theta \in [0,2\pi )$.