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

Abstract

Let $P$ be a set of $n$ points in the plane. We compute the value of $\hat{I}¸\in [0,2\ddot{I}€)$ for which the rectilinear convex hull of $P$, denoted by ${\mathcal{R}\mathcal{H}}_{\hat{I}}¸(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 $\hat{I}{\pm }_i$ be the sizes of the $2k$ angles defined by pairs of two consecutive lines, $i=1,\dots ,2k$. Let $\hat{I}{˜}_i=\ddot{I}€-\hat{I}{\pm }_i$ and $\hat{I}˜=\min \{\hat{I}{˜}_i:i=1,\dots ,2k\}$. We obtain: (1) Given a set $\mathcal{O}$ such that $\hat{I}˜\ge \frac{\ddot{I}}{€}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; If $\hat{I}˜<\frac{\ddot{I}}{€}2$, the time and space complexities are $O(\frac{n}{\hat{I}}˜\log n)$ and $O(\frac{n}{\hat{I}}˜)$ respectively. (2) Given a set $\mathcal{O}$ such that $\hat{I}˜\ge \frac{\ddot{I}}{€}2$, we compute and maintain the boundary of the ${\mathcal{O}}_{\hat{I}}¸$-convex hull of $P$ for $\hat{I}¸\in [0,2\ddot{I}€)$ in $O(kn\log n)$ time and $O(kn)$ space, or if $\hat{I}˜<\frac{\ddot{I}}{€}2$, in $O(k\frac{n}{\hat{I}}˜\log n)$ time and $O(k\frac{n}{\hat{I}}˜)$ space. (3) Finally, given a set $\mathcal{O}$ such that $\hat{I}˜\ge \frac{\ddot{I}}{€}2$, we compute, in $O(kn\log n)$ time and $O(kn)$ space, the angle $\hat{I}¸\in [0,2\ddot{I}€)$ such that the ${\mathcal{O}}_{\hat{I}}¸$-convex hull of $P$ has minimum (or maximum) area over all $\hat{I}¸\in [0,2\ddot{I}€)$.

28 pages, 23 figures. Accepted version