Gift Wrapping (Jarvis March)

Picture a handful of pins stuck into a corkboard. Now imagine stretching a piece of gift-wrap ribbon taut against the outermost pin, then swinging it around like a rigid arm until it snaps flat against the next outermost pin, then the next, and so on until the ribbon has come full circle. That physical motion — sweep, snap, sweep, snap — is precisely the gift wrapping algorithm, discovered by R. A. Jarvis in 1973 and often called the Jarvis march.

It solves the same problem as the convex hull: find the smallest convex polygon that encloses every point. But instead of sorting everything up front, gift wrapping builds the boundary one vertex at a time by always asking a single local question: "starting from the edge I just placed, which point is furthest around to the outside?"

It's slower than the fastest hull algorithms in the worst case, but it has a charming property: its running time scales with the size of the answer (the hull), not just the size of the input. Wrap a cloud of a million points that happens to have only five points on the boundary, and gift wrapping barely breaks a sweat.

Below is a scatter of points, with the leftmost (guaranteed to be on the hull) marked as the starting anchor. Press Step to pivot the wrapping ray one point at a time — watch it sweep counter-clockwise from the current hull edge until it locks onto the most extreme point, exactly like a taut ribbon snapping into place. Press Wrap fully to run the whole march at once, or Reset to scatter a fresh set of points.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="360" height="280"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="wrap" type="button">{{btn_wrap}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px;
         touch-action: none; max-width: 100%; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Notice what the ray is doing at every step: for each candidate point it checks whether that point lies clockwise or counter-clockwise of the current best guess, using nothing more than a cross product (no trigonometry, no sorting). The wrap finishes the moment the ray swings back to the anchor. Count the steps it took — that's exactly the number of vertices on the hull, no more, no less.

How hard is gift wrapping, really?

• Each pivot is cheap. To find the next hull point from the current one, scan all $n$ candidate points and keep whichever is most counter-clockwise, using the sign of a cross product to compare directions. That's an $O(n)$ scan per pivot.
• The number of pivots equals $h$, the number of vertices on the final hull. So the whole march costs $O(n \cdot h)$ — this is the classic gift wrapping / Jarvis march bound (Jarvis, 1973).
• It's in P, comfortably tractable — but notice the bound depends on two quantities, not just $n$. In the worst case $h = n$ (every point sits on the hull) and gift wrapping degrades to $O(n^{2})$, slower than the $O(n \log n)$ of Graham scan or Andrew's monotone chain. But when $h$ is small — a handful of extreme points surrounding a dense cloud — gift wrapping can be dramatically faster than sorting everything.
• This is called an output-sensitive algorithm: its cost scales with the size of what you're computing, not only with the size of what you feed it. Kirkpatrick and Seidel later showed an $O(n \log h)$ algorithm (the "ultimate convex hull algorithm," 1986) and proved that $\Omega(n \log h)$ is optimal — so gift wrapping's simplicity comes at a real, provable cost when $h$ grows large, but it is unbeatable in spirit when $h$ stays small.

The lesson generalizes far beyond geometry: sometimes the right question isn't "how big is the input?" but "how big is the answer?" — and an algorithm tuned to the second can beat one tuned only to the first.

Gift wrapping's output-sensitive nature makes it the natural choice whenever the hull is expected to be small compared to the input:

• Collision boundaries in games and physics engines: bounding shapes for clusters of objects are often small polygons wrapped around thousands of vertices, exactly gift wrapping's sweet spot.
• Higher-dimensional hulls: the same "pivot to the most extreme neighbor" idea generalizes to 3D and beyond, where output-sensitive behavior matters even more because point counts explode.
• GIS and cartography: tracing the outer boundary of a scattered set of survey points or sensor readings.
• Teaching computational geometry: because the algorithm mirrors a physical action anyone can picture, it's often the first hull algorithm students implement, before moving on to the faster but less intuitive sweep-based methods.

Understand gift wrapping and you've grasped the core idea behind output-sensitive algorithms — designs that adapt their cost to the size of the answer, a theme that echoes through the wider study of the convex hull and the limits explored across P vs NP.

Gift wrapping turns a childhood-simple physical motion — sweeping a taut ribbon around a scatter of pins — into a rigorous $O(nh)$ algorithm for the convex hull. Each pivot asks one honest local question (which point is furthest around?) and answers it with nothing fancier than a cross product.

It won't always be the fastest hull algorithm — when the hull is large, sorting-based methods like Graham scan win outright. But its output-sensitive cost is a small window into a bigger idea: sometimes the smartest algorithm is the one that measures its work against the size of the answer, not just the size of the input.