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 is an element of [0, 2 pi) for which the rectilinear convex hull of P, denoted by RHP(theta), has minimum (or maximum) area in optimal O(n log n) time and O(n) space, improving the previous O(n(2)) bound. Let O be a set of k lines through the origin sorted by slope and let ai be the sizes of the 2k angles defined by pairs of two consecutive lines, i = 1,..., 2k. Let Theta(i) = pi - alpha(i) and Theta = min{Theta(i) : i = 1,..., 2k}. We obtain: (1) Given a set O such that Theta >= pi/2, we provide an algorithm to compute the O-convex hull of P in optimal O(n log n) time and O(n) space; If Theta < pi/2, the time and space complexities are O(n/Theta log n) and O(n/Theta) respectively. (2) Given a set O such that Theta >= pi/2, we compute and maintain the boundary of the O-theta-convex hull of P for theta is an element of [0, 2 pi) in O(kn log n) time and O(kn) space, or if Theta < pi/2, in O(k n/Theta log n) time and O(k n/Theta) space. (3) Finally, given a set O such that Theta >= pi/2, we compute, in O(kn log n) time and O(kn) space, the angle theta is an element of [0, 2 pi) such that the O-theta-convex hull of P has minimum (or maximum) area over all theta is an element of [0, 2 pi).

Automated summary

This study focuses on the rectilinear convex hull of a set of points in the plane, presenting a method to compute the minimum area under different angles and their optimal time complexity. The sorting and analysis of lines are carried out based on the angle Theta.