Relative convex hull

The relative convex hull of a finite set of points in a simple polygon

In discrete geometry and computational geometry, the relative convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.

Definition

Let $P$ be a simple polygon or a rectifiable simple closed curve, and let $X$ be any set enclosed by $P$. A geodesic between two points in $P$ is a shortest path connecting those two points that stays entirely within $P$. A subset $K$ of the points inside $P$ is said to be relatively convex or $P$-convex if, for every two points of $K$, the geodesic between them in $P$ stays within $K$. Then the relative convex hull of $X$ can be defined as the intersection of all relatively convex sets containing $X$.

Special cases

Finite sets of points

The relative convex hull was first formulated for finite sets of points inside a simple polygon by Toussaint (1986), who provided an efficient algorithm for its construction. With subsequent improvements in the time bounds for finding shortest paths between query points in a polygon, and for polygon triangulation, this algorithm takes time $O(p+n\log(p+n))$ on an input with $n$ points in a polygon with $p$ vertices.

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

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. A simple polygon $P$ within another simple polygon $Q$ is relatively convex or $Q$-convex if every line segment contained in $Q$ that connects two points of $P$ lies within $P$. The relative convex hull of a simple polygon $P$ within $Q$ can be defined as the intersection of all $Q$-convex polygons that contain $P$, as the smallest $Q$-convex polygon that contains $P$, or as the minimum-perimeter simple polygon that contains $P$ and is contained by $Q$.

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.