On the definition and computation of rectilinear convex hulls (Q802314)

Unlike the classical convex hull, the definition of the rectilinear convex hull of a collection of points or of a collection of (rectilinear) polygons is fraught with difficulties. In this note three different approaches are discussed which have appeared in the literature. The three definitions are examined for point sets in general and some of their consequences are pointed out. Furthermore, optimal algorithms to compute the corresponding rectilinear convex hulls of a finite set of points in the plane are developed.