Optimizing an oriented convex hull with two directions
David Orden, Carlos Seara, Jorge Urrutia · 2015
Given a set P of n points in the plane in general position, we generalize the rectilinear convex hull of P , RH(P ), to the O 2 -convex hull of P , denoted byO 2 H(P ), where the directions of two oriented lines, used as coordinate axes, form an angle 2 [0; ]. We show: (i) How this hull can be computed and maintained while changes in [0; ], and (ii) How to determine the angle for whichO 2 H(P ) maximizes its area or minimizes its perimeter. Our algorithms run in optimal ( n logn) time and O(n) space.