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 )$$ θ ∈ [ 0 , 2 π ) for which the rectilinear convex hull of P, denoted by $$\mathcal {RH}_{P}({\theta })$$ RH P ( θ ) , has minimum (or maximum) area in optimal $$O(n\log n)$$ O ( n log n ) time and O(n) space, improving the previous $$O(n^2)$$ O ( n 2 ) bound. Let $$\mathcal {O}$$ O be a set of k lines through the origin sorted by slope and let $$\alpha _i$$ α i be the sizes of the 2k angles defined by pairs of two consecutive lines, $$i=1, \ldots , 2k$$ i = 1 , … , 2 k . Let $$\Theta _{i}=\pi -\alpha _i$$ Θ i = π - α i and $$\Theta =\min \{\Theta _i :i=1,\ldots ,2k\}$$ Θ = min { Θ i : i = 1 , … , 2 k } . We obtain: (1) Given a set $$\mathcal {O}$$ O such that $$\Theta \ge \frac{\pi }{2}$$ Θ ≥ π 2 , we provide an algorithm to compute the $$\mathcal {O}$$ O -convex hull of P in optimal $$O(n\log n)$$ O ( n log n ) time and O(n) space; If $$\Theta