Rectilinear and O-convex hull with minimum area

10/30/2017

∙

by   Carlos Alegría-Galicia, et al.

∙

0

∙

share

Let P be a set of n points in the plane and O be a set of k lines passing through the origin. We show: (1) How to compute the O-hull of P in Θ(n n) time and O(n) space, (2) how to compute and maintain the rotated hull OH_θ(P) for θ∈ [0,2π) in O(kn n) time and O(kn) space, and (3) how to compute in Θ(n n) time and O(n) space a value of θ for which the rectilinear convex hull, RH_θ(P), has minimum area, thus improving the previously best O(n^2) algorithm presented by Bae et al. in 2009.