Convex hull: Difference between revisions

Revision as of 20:40, 3 March 2025

Revision as of 11:22, 20 May 2025

Line 84:

===Simple polygons===

{{main|Convex hull of a simple polygon}}

[[File:Convex hull of a simple polygon.svg|thumb|upright|Convex hull ( in blue and yellow) of a simple polygon (in blue)]]

The convex hull of a [[simple polygon]] encloses the given polygon and is partitioned by it into regions, one of which is the polygon itself. The other regions, bounded by a [[polygonal chain]] of the polygon and a single convex hull edge, are called ''pockets''. Computing the same decomposition recursively for each pocket forms a hierarchical description of a given polygon called its ''convex differences tree''.{{sfnp|Rappoport|1992}} Reflecting a pocket across its convex hull edge expands the given simple polygon into a polygon with the same perimeter and larger area, and the [[Erdős–Nagy theorem]] states that this expansion process eventually terminates.{{sfnp|Demaine|Gassend|O'Rourke|Toussaint|2008}}