Relative convex hull

Toussaint (1986), who provided an efficient algorithm for the construction of the relative convex hull for finite sets of points inside a simple polygon.[3] With subsequent improvements in the time bounds for two subroutines, finding shortest paths between query points in a polygon,[4] and polygon triangulation,[5] this algorithm takes time ${\displaystyle O(p+n\log(p+n))}$ on an input with ${\displaystyle n}$ points in a polygon with ${\displaystyle p}$ vertices.[4] It can also be maintained dynamically in sublinear time per update.[6]

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.

For relative convex hulls of simple polygons, an alternative but equivalent definition of convexity can be used. A simple polygon ${\displaystyle P}$ within another simple polygon ${\displaystyle Q}$ is relatively convex or ${\displaystyle Q}$-convex if every line segment contained in ${\displaystyle Q}$ that connects two points of ${\displaystyle P}$ lies within ${\displaystyle P}$. The relative convex hull of a simple polygon ${\displaystyle P}$ within ${\displaystyle Q}$ can be defined as the intersection of all ${\displaystyle Q}$-convex polygons that contain ${\displaystyle P}$, as the smallest ${\displaystyle Q}$-convex polygon that contains ${\displaystyle P}$, or as the minimum-perimeter simple polygon that contains ${\displaystyle P}$ and is contained by ${\displaystyle Q}$.[1]

Klette (2010) 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.[1] Alternative linear time algorithms based on path planning are known.[7]

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,[8] and in data structures for collision detection of moving polygons.[9]