Orthogonal convex hull

From Wikipedia, the free encyclopedia

In Euclidean geometry, a set is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single interval. The orthogonal convex hull of a set 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 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 the x-y convex hull.

Contents 1 Example 2 Algorithms 3 Related concepts 4 References

[edit] 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 finite point set such as this one, all orthogonal convex hull edges are horizontal or vertical. In this example, the orthogonal convex hull is connected, but there exist planar point sets with disconnected orthogonal convex hulls.

[edit] Algorithms

Several authors have studied algorithms for constructing orthogonal convex hulls: Montuno and Fournier (1982); Nicholl et al. (1983); Ottman et al. (1984); Karlsson and 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.

[edit] 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 points with disconnected orthogonal hulls, or in higher dimensional Lp spaces.

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

[edit] References

• Fink, Eugene; Wood, Derick (1996). "Fundamentals of restricted-orientation convexity". Information sciences 92 (1–4): 175–196.

• Fink, Eugene; Wood, Derick (1998). "Generalized halfspaces in restricted-orientation convexity". Journal of Geometry 62: 99–120.

• 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: 456–471. DOI:10.1007/BF01933620.

• O'Rourke, Joseph (1993). Computational Geometry in C. Cambridge University Press, 107–109.

• Ottman, T.; Soisalon-Soisinen, E.; Wood, Derick (1984). "On the definition and computation of rectilinear convex hulls". Information Sciences 33: 157–171.

• 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: 150–166.

• Rawlins, G. J. E.; Wood, Derick (1988). Toussaint, Godfried T. (Ed.) "Ortho-convexity and its generalizations". Computational Morphology, 137–152, Elsevier.