In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.
Definition.
Let formula_1 be a simple polygon or a rectifiable simple closed curve, and let formula_2 be any set enclosed by formula_1.
A geodesic between two points in formula_1 is a shortest path connecting those two points that stays entirely within formula_1.
A subset formula_6 of the points inside formula_1 is said to be relatively convex, geodesically convex, or formula_1-convex if, for every two points of formula_6, the geodesic between them in formula_1 stays within formula_6. Then the relative convex hull of formula_2 can be defined as the intersection of all relatively convex sets containing formula_2.
Equivalently, the relative convex hull is the minimum-perimeter weakly simple polygon in formula_1 that encloses formula_2. This was the original formulation of relative convex hulls, by . 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 simple polygons when formula_2 is disconnected and its components are not all visible to each other.
Special cases.
Finite sets of points.
, who provided an efficient algorithm for the construction of the relative convex hull for finite sets of points inside a simple polygon. With subsequent improvements in the time bounds for two subroutines, finding shortest paths between query points in a polygon, and polygon triangulation, this algorithm takes time formula_17 on an input with formula_18 points in a polygon with formula_19 vertices. It can also be maintained dynamically in sublinear time per update.
The relative convex hull of a finite set of points is always a weakly simple polygon, 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.
Simple polygons.
For relative convex hulls of simple polygons, an alternative but equivalent definition of convexity can be used. A simple polygon formula_1 within another simple polygon formula_21 is relatively convex or formula_21-convex if every line segment contained in formula_21 that connects two points of formula_1 lies within formula_1. The relative convex hull of a simple polygon formula_1 within formula_21 can be defined as the intersection of all formula_21-convex polygons that contain formula_1, as the smallest formula_21-convex polygon that contains formula_1, or as the minimum-perimeter simple polygon that contains formula_1 and is contained by formula_21.
 generalizes linear time algorithms for the convex hull of a simple polygon 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. Alternative linear time algorithms based on path planning are known.
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, and in data structures for collision detection of moving polygons.
Higher dimensions.
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. 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;