Orthogonal convex hull

The orthogonal convex hull of a point set

In geometry, a set K ⊂ Rⁿ 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 ⊂ Rⁿ 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 L^p spaces.

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

References

• Fink, Eugene; Wood, Derick (1996), "Fundamentals of restricted-orientation convexity" (PDF), Information Sciences, 92 (1–4): 175–196, doi:10.1016/0020-0255(96)00056-4 .
• Fink, Eugene; Wood, Derick (1998), "Generalized halfspaces in restricted-orientation convexity" (PDF), Journal of Geometry, 62: 99–120, doi:10.1007/BF01237603 .
• Karlsson, Rolf G.; Overmars, Mark H. (1988), "Scanline algorithms on a grid", BIT, 28 (2): 227–241, doi:10.1007/BF01934088 .
• Montuno, D. Y.; Fournier, A. (1982), Finding the x-y convex hull of a set of x-y polygons, Technical Report 148, University of Toronto .
• Nicholl, T. M.; Lee, D. T.; Liao, Y. Z.; Wong, C. K. (1983), "On the X-Y convex hull of a set of X-Y polygons", BIT, 23 (4): 456–471, doi:10.1007/BF01933620 .
• O'Rourke, Joseph (1993), Computational Geometry in C, Cambridge University Press, pp. 107–109 .
• Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), "On the definition and computation of rectilinear convex hulls", Information Sciences, 33 (3): 157–171, doi:10.1016/0020-0255(84)90025-2 .
• Rawlins, G. J. E. (1987), Explorations in Restricted-Orientation Geometry, Ph.D. thesis and Tech. Rep. CS-87-57, University of Waterloo .
• Rawlins, G. J. E.; Wood, Derick (1987), "Optimal computation of finitely oriented convex hulls", Information and Computation, 72 (2): 150–166, doi:10.1016/0890-5401(87)90045-9 .
• Rawlins, G. J. E.; Wood, Derick (1988), "Ortho-convexity and its generalizations", in Toussaint, Godfried T., Computational Morphology, Elsevier, pp. 137–152 .