On theO-hull of planar point sets
Carlos Alegr, David Orden, Carlos Seara · 2014
Let P be a set of n points in the plane and O be a set of k, 2 ≤ k ≤ n, different orientations in the plane sorted in counterclockwise circular order, such that the biggest angle defined by two consecutive orientations is at most π2 . We show: (1) How to compute the oriented O-hull of P in optimal Θ(n log n) time and O(n) space, (2) how to compute the unoriented O-hull of P in O(kn log n) time and O(kn) space, and (3) how to solve the problem of computing an orientation of the plane for which the O-hull of P has minimum area in O(kn log n) time and O(kn) space.