Relative convex hull

<h2 id="definition">Definition</h2>
Let 
 
 
 
 P
 
 
 {\displaystyle P}
 
 be a simple polygon or a rectifiable simple closed curve, and let 
 
 
 
 X
 
 
 {\displaystyle X}
 
 be any set enclosed by 
 
 
 
 P
 
 
 {\displaystyle P}
 
.
A <a href="/facts/Geodesic/fbWR6l80">geodesic</a> between two points in 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is a shortest path connecting those two points that stays entirely within 
 
 
 
 P
 
 
 {\displaystyle P}
 
.
A subset 
 
 
 
 K
 
 
 {\displaystyle K}
 
 of the points inside 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is said to be relatively convex, geodesically convex, or 
 
 
 
 P
 
 
 {\displaystyle P}
 
-convex if, for every two points of 
 
 
 
 K
 
 
 {\displaystyle K}
 
, the geodesic between them in 
 
 
 
 P
 
 
 {\displaystyle P}
 
 stays within 
 
 
 
 K
 
 
 {\displaystyle K}
 
. Then the relative convex hull of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 can be defined as the intersection of all relatively convex sets containing 
 
 
 
 X
 
 
 {\displaystyle X}
 
.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Equivalently, the relative convex hull is the minimum-perimeter <a href="/facts/Weakly_simple_polygon/C5CfrPWf">weakly simple polygon</a> in 
 
 
 
 P
 
 
 {\displaystyle P}
 
 that encloses 
 
 
 
 X
 
 
 {\displaystyle X}
 
. This was the original formulation of relative convex hulls, by Sklansky, Chazin & Hansen (1972).<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> However this definition is complicated by the need to use weakly simple polygons (intuitively, polygons in which the polygon boundary can touch or overlap itself but not cross itself) instead of <a href="/facts/Simple_polygon/C5CfrPWf">simple polygons</a> when 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is disconnected and its components are not all visible to each other.

<h2 id="special-cases">Special cases</h2>
<h3>Finite sets of points</h3>
Toussaint (1986), who provided an efficient algorithm for the construction of the relative convex hull for finite sets of points inside a <a href="/facts/Simple_polygon/C5CfrPWf">simple polygon</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> With subsequent improvements in the time bounds for two subroutines, finding shortest paths between query points in a polygon,<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> and <a href="/facts/Polygon_triangulation/FF0205ye">polygon triangulation</a>,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> this algorithm takes time 
 
 
 
 O
 (
 p
 +
 n
 log
 ⁡
 (
 p
 +
 n
 )
 )
 
 
 {\displaystyle O(p+n\log(p+n))}
 
 on an input with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points in a polygon with 
 
 
 
 p
 
 
 {\displaystyle p}
 
 vertices.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> It can also be maintained <a href="/facts/Dynamic_convex_hull/FXwqnjf9">dynamically</a> in sublinear time per update.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
The relative convex hull of a finite set of points is always a <a href="/facts/Weakly_simple_polygon/C5CfrPWf">weakly simple polygon</a>, but it might not actually be a simple polygon, because parts of it can be connected to each other by line segments or polygonal paths rather than by regions of nonzero area.

<h3>Simple polygons</h3>
For relative convex hulls of simple polygons, an alternative but equivalent definition of convexity can be used. A simple polygon 
 
 
 
 P
 
 
 {\displaystyle P}
 
 within another simple polygon 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 is relatively convex or 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
-convex if every line segment contained in 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 that connects two points of 
 
 
 
 P
 
 
 {\displaystyle P}
 
 lies within 
 
 
 
 P
 
 
 {\displaystyle P}
 
. The relative convex hull of a simple polygon 
 
 
 
 P
 
 
 {\displaystyle P}
 
 within 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 can be defined as the intersection of all 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
-convex polygons that contain 
 
 
 
 P
 
 
 {\displaystyle P}
 
, as the smallest 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
-convex polygon that contains 
 
 
 
 P
 
 
 {\displaystyle P}
 
, or as the minimum-perimeter simple polygon that contains 
 
 
 
 P
 
 
 {\displaystyle P}
 
 and is contained by 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
Klette (2010) generalizes <a href="/facts/Linear_time/77T62gmf">linear time</a> algorithms for the <a href="/facts/Convex_hull_of_a_simple_polygon/ssfd5A1g">convex hull of a simple polygon</a> to the relative convex hull of one simple polygon within another. The resulting generalized algorithm is not linear time, however: its time complexity depends on the depth of nesting of certain features of one polygon within another. In this case, the relative convex hull is itself a simple polygon.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Alternative linear time algorithms based on <a href="/facts/Path_planning/DoSPv4dB">path planning</a> are known.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
A similar definition can also be given for the relative convex hull of two disjoint simple polygons. This type of hull can be used in algorithms for testing whether the two polygons can be separated into disjoint halfplanes by a continuous linear motion,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> and in data structures for <a href="/facts/Collision_detection/kXkE9WXv">collision detection</a> of moving polygons.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="higher-dimensions">Higher dimensions</h2>
The definition of relative convex hulls based on minimum enclosure does not extend to higher dimensions, because (even without being surrounded by an outer shape) the minimum surface area enclosure of a non-convex set is not generally convex.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> However, for the relative convex hull of a connected set within another set, a similar definition to one for simple polygons can be used. In this case, a relatively convex set can again be defined as a subset of the given outer set that contains all line segments in the outer set between pairs of its points. The relative convex hull can be defined as the intersection of all relatively convex sets that contain the inner set.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Klette, Gisela (November 2010), "A recursive algorithm for calculating the relative convex hull", 25th International Conference of Image and Vision Computing New Zealand, IEEE, pp. 1–7, doi:10.1109/ivcnz.2010.6148857, ISBN 978-1-4244-9631-0, S2CID 17854252 <a href="978-1-4244-9631-0" target="_blank">978-1-4244-9631-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sklansky, Jack; Chazin, Robert L.; Hansen, Bruce J. (1972), "Minimum-perimeter polygons of digitized silhouettes", IEEE Transactions on Computers, C-21 (3): 260–268, doi:10.1109/tc.1972.5008948, S2CID 6818423 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Toussaint, Godfried (1986), "An optimal algorithm for computing the relative convex hull of a set of points in a polygon", Proceedings of EURASIP, Signal Processing III: Theories and Applications, Part 2, North-Holland, pp. 853–856 <a href="/wiki/Godfried_Toussaint" target="_blank">/wiki/Godfried_Toussaint</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Guibas, Leonidas J.; Hershberger, John (1989), "Optimal shortest path queries in a simple polygon", Journal of Computer and System Sciences, 39 (2): 126–152, doi:10.1016/0022-0000(89)90041-X, MR 1024124 <a href="/wiki/Leonidas_J._Guibas" target="_blank">/wiki/Leonidas_J._Guibas</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Chazelle, Bernard (1991), "Triangulating a simple polygon in linear time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703 <a href="/wiki/Bernard_Chazelle" target="_blank">/wiki/Bernard_Chazelle</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Guibas, Leonidas J.; Hershberger, John (1989), "Optimal shortest path queries in a simple polygon", Journal of Computer and System Sciences, 39 (2): 126–152, doi:10.1016/0022-0000(89)90041-X, MR 1024124 <a href="/wiki/Leonidas_J._Guibas" target="_blank">/wiki/Leonidas_J._Guibas</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Oh, Eunjin; Ahn, Hee-Kap (2017), "Dynamic geodesic convex hulls in dynamic simple polygons", 33rd International Symposium on Computational Geometry (SoCG 2017), LIPIcs, vol. 77, Schloss Dagstuhl, pp. 51:1–51:15, doi:10.4230/LIPIcs.SoCG.2017.51, MR 3685723 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Klette, Gisela (November 2010), "A recursive algorithm for calculating the relative convex hull", 25th International Conference of Image and Vision Computing New Zealand, IEEE, pp. 1–7, doi:10.1109/ivcnz.2010.6148857, ISBN 978-1-4244-9631-0, S2CID 17854252 <a href="978-1-4244-9631-0" target="_blank">978-1-4244-9631-0</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Klette, Gisela (November 2010), "A recursive algorithm for calculating the relative convex hull", 25th International Conference of Image and Vision Computing New Zealand, IEEE, pp. 1–7, doi:10.1109/ivcnz.2010.6148857, ISBN 978-1-4244-9631-0, S2CID 17854252 <a href="978-1-4244-9631-0" target="_blank">978-1-4244-9631-0</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Williams, Jason; Rossignac, Jarek (2005), "Tightening: curvature-limiting morphological simplification", in Kobbelt, Leif; Shapiro, Vadim (eds.), Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, pp. 107–112, doi:10.1145/1060244.1060257, hdl:1853/3736, S2CID 15514388 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Toussaint, Godfried (1989), "On separating two simple polygons by a single translation", Discrete & Computational Geometry, 4 (3): 265–278, doi:10.1007/BF02187729, MR 0988749 <a href="/wiki/Godfried_Toussaint" target="_blank">/wiki/Godfried_Toussaint</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Basch, Julien; Erickson, Jeff; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2004), "Kinetic collision detection between two simple polygons", Computational Geometry, 27 (3): 211–235, doi:10.1016/j.comgeo.2003.11.001, MR 2039172, S2CID 300999 <a href="/wiki/Leonidas_J._Guibas" target="_blank">/wiki/Leonidas_J._Guibas</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Williams, Jason; Rossignac, Jarek (2005), "Tightening: curvature-limiting morphological simplification", in Kobbelt, Leif; Shapiro, Vadim (eds.), Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, pp. 107–112, doi:10.1145/1060244.1060257, hdl:1853/3736, S2CID 15514388 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Sloboda, Fridrich; Za'ko, Bedrich (2001), "On approximation of Jordan surfaces in 3d", in Bertrand, G.; Imiya, A.; Klette, R. (eds.), Digital and Image Geometry: Advanced Lectures, Lecture Notes in Computer Science, vol. 2243, Springer, pp. 365–386, doi:10.1007/3-540-45576-0_22, ISBN 978-3-540-43079-7 <a href="978-3-540-43079-7" target="_blank">978-3-540-43079-7</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Relative convex hull open-in-new

Relative convex hull