Orthogonal convex hull

<h2 id="example">Example</h2>
<p>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 <a href="/facts/Polygon/yAq7RjPz">polygon</a> 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.
</p>
<h2 id="alternative-definitions">Alternative definitions</h2>

<p>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
        ⊂
        
          
            R
          
          
            d
          
        
      
    
    {\displaystyle K\subset \mathbb {R} ^{d}}
  
:
</p>
<ol><li>Maximal definition: The definition described in the introduction of this article. It is based on the <a href="/facts/Maxima_of_a_point_set/fFMNtz11">Maxima of a point set</a>.</li>
<li>Classical definition: The orthogonal convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
 is the intersection of all orthogonally convex <a href="/facts/Superset/SJGERmbA">supersets</a> of 
  
    
      
        K
      
    
    {\displaystyle K}
  
; Ottmann, Soisalon-Soininen & Wood (1984).</li>
<li>Connected definition: The orthogonal convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
 is the smallest connected orthogonally convex superset of 
  
    
      
        K
      
    
    {\displaystyle K}
  
; Nicholl et al. (1983).</li>
<li>Functional definition: The orthogonal convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
 is the intersection of the <a href="/facts/Zero_set/mlK3dhoT">zero sets</a> of all non-negative orthogonally convex functions that are 
  
    
      
        0
      
    
    {\displaystyle 0}
  
 on 
  
    
      
        K
      
    
    {\displaystyle K}
  
; Matoušek & Plecháč (1998).</li></ol>
<p>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 <a href="/facts/Polygon/yAq7RjPz">polygon</a> with some degenerate "edges", namely, orthogonally convex alternating <a href="/facts/Polygonal_chain/GRQ6BMQS">polygonal chains</a> with interior angle 
  
    
      
        
          90
          
            ∘
          
        
      
    
    {\displaystyle 90^{\circ }}
  
 connecting extreme vertices.
</p>
<h3>Classical orthogonal convex hull</h3>
<p>The classical orthogonal convex hull can be equivalently defined as the smallest orthogonally convex superset of a set 
  
    
      
        K
        ⊂
        
          
            R
          
          
            2
          
        
      
    
    {\displaystyle K\subset \mathbb {R} ^{2}}
  
, by analogy to the following definition of the convex hull: <i>the convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
 is the smallest convex superset of 
  
    
      
        K
      
    
    {\displaystyle K}
  
</i>. The classical orthogonal convex hull might be disconnected. If a point set has no pair of points on a line parallel to one of the standard basis vectors, the classical orthogonal convex hull of such point set is equal to the point set itself.
</p><p>A well known property of convex hulls is derived from the <a href="/facts/Carath%25C3%25A9odory%2527s_theorem_(convex_hull)/QGyEIEPv">Carathéodory's theorem</a>: A point 
  
    
      
        x
        ∈
        
          
            R
          
          
            d
          
        
      
    
    {\displaystyle x\in \mathbb {R} ^{d}}
  
 is in the interior of the convex hull of a point set 
  
    
      
        K
        ⊂
        
          
            R
          
          
            d
          
        
      
    
    {\displaystyle K\subset \mathbb {R} ^{d}}
  
 if, and only if, it is already in the convex hull of 
  
    
      
        d
        +
        1
      
    
    {\displaystyle d+1}
  
 or fewer points of 
  
    
      
        K
      
    
    {\displaystyle K}
  
. This property is also valid for classical orthogonal convex hulls.
</p>
<h3>Connected orthogonal convex hull</h3>
<p>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
          
            ∘
          
        
      
    
    {\displaystyle 90^{\circ }}
  
 connecting the points. Any such polygonal chain has the same length, so there are infinitely many connected orthogonal convex hulls for the point set.
</p><p>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
        ⊂
        
          
            R
          
          
            2
          
        
      
    
    {\displaystyle K\subset \mathbb {R} ^{2}}
  
 is connected, then it is equal to the connected orthogonal convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
. If this is not the case, then there are infinitely many connected orthogonal convex hulls for 
  
    
      
        K
      
    
    {\displaystyle K}
  
, and each one can be obtained by joining the connected components of the maximal orthogonal convex hull of 
  
    
      
        K
      
    
    {\displaystyle K}
  
 with orthogonally convex alternating polygonal chains with interior angle 
  
    
      
        
          90
          
            ∘
          
        
      
    
    {\displaystyle 90^{\circ }}
  
.
</p>
<h3>Functional orthogonal convex hull</h3>
<p>The functional orthogonal convex hull is not defined using properties of sets, but properties of functions about sets. Namely, it restricts the notion of <a href="/facts/Convex_function/IbzG5SLF">convex function</a> as follows. A function 
  
    
      
        f
        :
        
          
            R
          
          
            d
          
        
        →
        
          R
        
      
    
    {\displaystyle f:\mathbb {R} ^{d}\rightarrow \mathbb {R} }
  
 is called orthogonally convex if its restriction to each line parallel to a non-zero of the standard basis vectors is a convex function.
</p>
<h2 id="algorithms">Algorithms</h2>
<p>Several authors have studied algorithms for constructing orthogonal convex hulls: Montuno & Fournier (1982); Nicholl et al. (1983); Ottmann, Soisalon-Soininen & Wood (1984); Karlsson & Overmars (1988). By the results of these authors, the orthogonal convex hull of n points in the plane may be constructed in time <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>n</i> <a href="/facts/Logarithm/QeXaV97q">log</a> <i>n</i>), or possibly faster using integer searching data structures for points with <a href="/facts/Integer/PUwwrawx">integer</a> coordinates.
</p>
<h2 id="related-concepts">Related concepts</h2>
<p>It is natural to generalize orthogonal convexity to <i>restricted-orientation convexity</i>, in which a set K is defined to be convex if all lines having one of a <a href="/facts/Finite_set/za1newlP">finite set</a> of slopes must intersect K in connected subsets; see e.g. Rawlins (1987), Rawlins and Wood (1987, 1988), or Fink and Wood (1996, 1998).
</p><p>In addition, the <a href="/facts/Tight_span/vSWExdHm">tight span</a> of a finite <a href="/facts/Metric_space/gnBBRXtc">metric space</a> 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 <a href="/facts/Manhattan_distance/zU7gGUPv">Manhattan distance</a> on the point set. However, orthogonal hulls and tight spans differ for point sets with disconnected orthogonal hulls, or in higher-dimensional <a href="/facts/Lp_space/gbad0Rv1">L<i>p</i> spaces</a>.
</p><p>O'Rourke (1993) describes several other results about orthogonal convexity and orthogonal <a href="/facts/Visibility_(geometry)/Wu1C49qu">visibility</a>.
</p>

<ul><li>Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), <a href="http://cse.iitkgp.ac.in/%7Epb/research/ohull/ohull.html">"A Linear-time Combinatorial Algorithm to Find the Orthogonal Hull of an Object on the Digital Plane"</a>, <i>Information Sciences</i>, 216: 176–195, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ins.2012.05.029">10.1016/j.ins.2012.05.029</a>.</li>
<li>Fink, Eugene; <a href="/facts/Derick_Wood/dGFHnzJG">Wood, Derick</a> (1996), <a href="https://www.cs.cmu.edu/~eugene/research/full/restricted-convexity.pdf">"Fundamentals of restricted-orientation convexity"</a> (PDF), <i>Information Sciences</i>, 92 (1–4): 175–196, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0255%2896%2900056-4">10.1016/0020-0255(96)00056-4</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17771224">17771224</a>.</li>
<li>Fink, Eugene; <a href="/facts/Derick_Wood/dGFHnzJG">Wood, Derick</a> (1998), <a href="https://www.cs.cmu.edu/~eugene/research/full/restricted-halfspaces.pdf">"Generalized halfspaces in restricted-orientation convexity"</a> (PDF), <i>Journal of Geometry</i>, 62 (1–2): 99–120, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01237603">10.1007/BF01237603</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14709697">14709697</a>.</li>
<li>Karlsson, Rolf G.; <a href="/facts/Mark_Overmars/4MzGpDBq">Overmars, Mark H.</a> (1988), "Scanline algorithms on a grid", <i>BIT</i>, 28 (2): 227–241, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01934088">10.1007/BF01934088</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1874%2F16270">1874/16270</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:32964283">32964283</a>.</li>
<li>Matoušek, J.; Plecháč, P. (1998), "On Functional Separately Convex Hulls", <i>Discrete & Computational Geometry</i>, 19 (1): 105–130, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FPL00009331">10.1007/PL00009331</a>.</li>
<li>Montuno, D. Y.; Fournier, A. (1982), <i>Finding the x-y convex hull of a set of x-y polygons</i>, Technical Report 148, University of Toronto.</li>
<li>Nicholl, T. M.; <a href="/facts/Der-Tsai_Lee/L5xxgPdK">Lee, D. T.</a>; Liao, Y. Z.; Wong, C. K. (1983), "On the X-Y convex hull of a set of X-Y polygons", <i>BIT</i>, 23 (4): 456–471, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01933620">10.1007/BF01933620</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:10492640">10492640</a>.</li>
<li><a href="/facts/Joseph_O%2527Rourke_(professor)/4katVCtw">O'Rourke, Joseph</a> (1993), <i>Computational Geometry in C</i>, Cambridge University Press, pp. 107–109.</li>
<li>Ottmann, T.; Soisalon-Soininen, E.; <a href="/facts/Derick_Wood/dGFHnzJG">Wood, Derick</a> (1984), "On the definition and computation of rectilinear convex hulls", <i>Information Sciences</i>, 33 (3): 157–171, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0255%2884%2990025-2">10.1016/0020-0255(84)90025-2</a>.</li>
<li>Rawlins, G. J. E. (1987), <i>Explorations in Restricted-Orientation Geometry</i>, Ph.D. thesis and Tech. Rep. CS-87-57, University of Waterloo.</li>
<li>Rawlins, G. J. E.; <a href="/facts/Derick_Wood/dGFHnzJG">Wood, Derick</a> (1987), "Optimal computation of finitely oriented convex hulls", <i>Information and Computation</i>, 72 (2): 150–166, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0890-5401%2887%2990045-9">10.1016/0890-5401(87)90045-9</a>.</li>
<li>Rawlins, G. J. E.; <a href="/facts/Derick_Wood/dGFHnzJG">Wood, Derick</a> (1988), "Ortho-convexity and its generalizations", in <a href="/facts/Godfried_Toussaint/AN8GxkAS">Toussaint, Godfried T.</a> (ed.), <i>Computational Morphology</i>, Elsevier, pp. 137–152.</li></ul>

Orthogonal convex hull open-in-new

Orthogonal convex hull