Orthogonal convex hull

In geometry, a set K ⊂ Rd is defined to be orthogonally convex if, for every line L that is parallel to one of standard basis vectors, the intersection of K with L is empty, a point, or a single segment.

As can be seen in the figure, the orthogonal convex hull is a polygon with some degenerate edges connecting extreme vertices in each coordinate direction.

For a discrete point set such as this one, all orthogonal convex hull edges are horizontal or vertical.

So far, researchers have explored the following four definitions of the orthogonal convex hull of a set

From top to bottom, the second to the fourth figures show respectively, the maximal, the connected, and the functional orthogonal convex hull of the point set.

As can be seen, the orthogonal convex hull is a polygon with some degenerate "edges", namely, orthogonally convex alternating polygonal chains with interior angle

A well known property of convex hulls is derived from the Carathéodory's theorem: A point

This property is also valid for classical orthogonal convex hulls.

Consider for example a pair of points in the plane not lying on an horizontal or a vertical line.

Any such polygonal chain has the same length, so there are infinitely many connected orthogonal convex hulls for the point set.

If the maximal orthogonal convex hull of a point set

If this is not the case, then there are infinitely many connected orthogonal convex hulls for

, and each one can be obtained by joining the connected components of the maximal orthogonal convex hull of

with orthogonally convex alternating polygonal chains with interior angle

Several authors have studied algorithms for constructing orthogonal convex hulls: Montuno & Fournier (1982); Nicholl et al. (1983); Ottmann, Soisalon-Soininen & Wood (1984); Karlsson & Overmars (1988).

By the results of these authors, the orthogonal convex hull of n points in the plane may be constructed in time O(n log n), or possibly faster using integer searching data structures for points with integer coordinates.

In addition, the tight span of a finite metric space is closely related to the orthogonal convex hull.

If a finite point set in the plane has a connected orthogonal convex hull, that hull is the tight span for the Manhattan distance on the point set.

The orthogonal convex hull of a point set
A set of six points in the plane. The Classical Ortho-convex Hull is the point set it self.
The Maximal Ortho-convex Hull of the point set of the top figure. It is formed by the point set and the colored area.
A Connected Ortho-convex Hull of the point set of the top figure. It is formed by the point set, the colored area and the two ortho-convex polygonal chains.
The Functional Ortho-convex Hull of the point set of the top figure. It is formed by the point set, the colored area, and the four line segments.