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 axisaligned 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 xy convex hull. Contents 1 Example 2 Algorithms 3 Related concepts 4 References Example[edit]
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[edit]
Several authors have studied algorithms for constructing orthogonal
convex hulls: Montuno & Fournier (1982); Nicholl et al. (1983);
Ottmann, SoisalonSoininen & 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[edit]
It is natural to generalize orthogonal convexity to
restrictedorientation 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
Fink, Eugene; Wood, Derick (1996), "Fundamentals of
restrictedorientation convexity" (PDF), Information Sciences, 92
(1–4): 175–196, doi:10.1016/00200255(96)000564 .
Fink, Eugene; Wood, Derick (1998), "Generalized halfspaces in
restrictedorientation 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 xy convex hull of a
set of xy polygons, Technical Report 148, University of
Toronto .
Nicholl, T. M.; Lee, D. T.; Liao, Y. Z.; Wong, C. K. (1983), "On the
XY convex hull of a set of XY polygons", BIT, 23 (4): 456–471,
doi:10.1007/BF01933620 .
O'Rourke, Joseph (1993), Computational
Geometry
