Relative convex hull

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.

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

Definition

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

Equivalently, the relative convex hull is the minimum-perimeter weakly simple polygon in ${\displaystyle P}$ that encloses ${\displaystyle X}$. This was the original formulation of relative convex hulls, by Sklansky, Chazin & Hansen (1972).[2] 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 ${\displaystyle X}$ is disconnected and its components are not all visible to each other.

Special cases

Finite sets of points

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.

Simple polygons

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]

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.[7] 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.[10]

References

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, doi:10.1109/ivcnz.2010.6148857
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
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
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
5. Chazelle, Bernard (1991), "Triangulating a simple polygon in linear time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703
6. Oh, Eunjin; Ahn, Hee-Kap (2017), "Dynamic geodesic convex hulls in dynamic simple polygons", 33rd International Symposium on Computational Geometry (SoCG 2017), LIPIcs, 77, Schloss Dagstuhl, pp. 51:1–51:15, doi:10.4230/LIPIcs.SoCG.2017.51, MR 3685723
7. 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
8. 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
9. 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
10. 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, 2243, Springer, pp. 365–386, doi:10.1007/3-540-45576-0_22