Computational Geometry: An Introduction (Texts and Monographs in Computer Science)

Category: Mathematics
Author: Franco P. Preparata, Michael I. Shamos
This Month Stack Overflow 1


by anonymous   2019-01-13

I think what you want to compute is the Rectilinear Convex Hull (or Orthogonal Convex Hull) of the set of points. The rectilinear convex hull is an ortho-convex shape, that is, the intersection of the shape with any horizontal or vertical line results in an empty set, a point, or a line segment.

The vertices of the rectilinear convex hull are the set of maximal points under vector dominance. The rectilinear convex hull can then be computed in optimal O(n log n) time. A very simple algorithm is presented in Preparata's book on Computational Geometry (see the section 4.1.3).