In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.
The orthogonal convex hull of a set is the intersection of all connected orthogonally convex supersets of .
These definitions are made by analogy with the classical theory of convexity, in which is convex if, for every line, the intersection of with is empty, a point, or a single segment. Orthogonal convexity restricts the lines for which this property is required to hold, so every convex set is orthogonally convex but not vice versa. For the same reason, the orthogonal convex hull itself is a subset of the convex hull of the same point set. A point belongs to the orthogonal convex hull of if and only if each of the closed axis-aligned orthants having as apex has a nonempty intersection with .
The orthogonal convex hull is also known as the rectilinear convex hull, or, in two dimensions, the - convex hull.
The figure shows a set of 16 points in the plane and the orthogonal convex hull of these points. 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. In this example, the orthogonal convex hull is connected.
In contrast with the classical convexity where there exist several equivalent definitions of the convex hull, definitions of the orthogonal convex hull made by analogy to those of the convex hull result in different geometric objects. So far, researchers have explored the following four definitions of the orthogonal convex hull of a set
K\subset\Rd
K
K
K
K
K
0
K
In the figures on the right, the top figure shows a set of six points in the plane. The classical orthogonal convex hull of the point set is the point set itself. 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
90\circ
The classical orthogonal convex hull can be equivalently defined as the smallest orthogonally convex superset of a set
K\subset\R2
K
K
A well known property of convex hulls is derived from the Carathéodory's theorem: A point
x\in\Rd
K\subset\Rd
d+1
K
By definition, the connected orthogonal convex hull is always connected. However, it is not unique. Consider for example a pair of points in the plane not lying on an horizontal or a vertical line. The connected orthogonal convex hull of such points is an orthogonally convex alternating polygonal chain with interior angle
90\circ
For point sets in the plane, the connected orthogonal convex hull can be easily obtained from the maximal orthogonal convex hull. If the maximal orthogonal convex hull of a point set
K\subset\R2
K
K
K
90\circ
The functional orthogonal convex hull is not defined using properties of sets, but properties of functions about sets. Namely, it restricts the notion of convex function as follows. A function
f:\Rd → \R
Several authors have studied algorithms for constructing orthogonal convex hulls: ; ; ; . By the results of these authors, the orthogonal convex hull of points in the plane may be constructed in time, or possibly faster using integer searching data structures for points with integer coordinates.
It is natural to generalize orthogonal convexity to restricted-orientation convexity, in which a set is defined to be convex if all lines having one of a finite set of slopes must intersect in connected subsets; see e.g.,, or .
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. However, orthogonal hulls and tight spans differ for point sets with disconnected orthogonal hulls, or in higher-dimensional Lp spaces.
describes several other results about orthogonal convexity and orthogonal visibility.