Universidad Nacional Autónoma de México
Thursday, April 26 at 3:00 PM
A region in the plane is ortho-convex if its intersection with any line parallel to a coordinate axis is either empty or connected. Given a point set P of n points in the plane, the Rectilinear Convex Hull of P is the intersection of all connected supersets of P that are ortho-convex. In contrast to the standard convex hull of P, the rectilinear convex hull is a non-convex, possibly disconnected, and orientation dependent region. Well known applications of the rectilinear convex hull can be found in polyhedra reconstruction, VLSI circuit layout design, and pattern recognition from digital images.
In this talk we discuss computational problems related to the rectilinear convex hull of a set of points in the plane, and show how they generalize to the restricted-orientation convex hull. We will describe an optimal O(n log n) time algorithm to compute the rectilinear convex hull of P with minimum area over all orientations of the plane. Consider that P is equal to the union of two disjoint sets of red and blue points. We show how to preprocess P in optimal O(n log n) time so that the inclusion between the blue and the red rectilinear convex hulls can be tested in optimal O(log n) time.