Orthogonal convex hull

The orthogonal convex hull of a point set

In geometry, a set K ⊂ Rn 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. 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 S ⊂ Rn is the intersection of all connected orthogonally convex supersets of S.

These definitions are made by analogy with the classical theory of convexity, in which K is convex if, for every line L, the intersection of K with L is empty, a point, or a single segment (interval). 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 p belongs to the orthogonal convex hull of S if and only if each of the closed axis-aligned orthants having p as apex has a nonempty intersection with S.

The orthogonal convex hull is also known as the rectilinear convex hull, or, in two dimensions, the x-y convex hull.

Example

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.

Algorithms

Several authors have studied algorithms for constructing orthogonal convex hulls: Montuno & Fournier (1982); Nicholl et al. (1983); Ottman, Soisalon-Soisinen & Wood (1984); Karlsson & Overmars (1988). By the results of these authors, the orthogonal convex hull of k points in the plane may be constructed in time O(k log k), or possibly faster using integer searching data structures for points with integer coordinates.

Related concepts

It is natural to generalize orthogonal convexity to restricted-orientation convexity, in which a set K is defined to be convex if all lines having one of a finite set of slopes must intersect K in connected subsets; see e.g. Rawlins (1987), Rawlins and Wood (1987, 1988), or Fink and Wood (1996, 1998).

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.

O'Rourke (1993) describes several other results about orthogonal convexity and orthogonal visibility.

References

This article is issued from Wikipedia - version of the Wednesday, July 22, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.