Introduction

Take five points on a page, no three of them in a straight line. Try as hard as you like to scatter them so that no four form the corners of a convex quadrilateral — a four-sided shape with no dent in it. You will fail. Every single time, some four of the five points line up into a convex shape.

This little fact was discovered in the 1930s by a group of young mathematicians in Budapest, among them Esther Klein, who first noticed the pattern, and George Szekeres, who worked with Paul Erdős to prove it in general. The story has a twist: Klein and Szekeres fell in love while chasing the proof and eventually married — which is why Erdős nicknamed it the Happy Ending problem.

But the cute love story hides a genuinely hard mathematical question. Five points always force a convex quadrilateral. How many points does it take to force a convex pentagon? A convex hexagon? A convex shape with nn corners? That question, asked almost a century ago, is still not fully answered.

Try It Yourself

Click anywhere on the canvas to drop points, one at a time. As soon as you have placed five points (no three in a line), press Find the convex quadrilateral and watch the computer highlight four of them that always form a convex shape.

<p class="hint">Click the canvas to place up to <b>5</b> points (try to avoid three in a straight line). Whatever pattern you choose, four of your points will always form the corners of a convex quadrilateral — a four-sided shape with no dent in it.</p>
<svg id="canvas" class="canvas" viewBox="0 0 360 260" role="img" aria-label="Canvas for placing points to test the Happy Ending problem"></svg>
<div class="status" id="status">Click to place a point.</div>
<div class="btns">
  <button id="find" type="button">Find the convex quadrilateral</button>
  <button id="reset" type="button" class="ghost">Clear</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 { width: 100%; max-width: 360px; height: 260px; background: #f4f6f8; border: 1px solid #cdd9e3;
          border-radius: 8px; display: block; cursor: crosshair; touch-action: manipulation; }
.pt { fill: #1d3557; stroke: #fff; stroke-width: 1.5; }
.pt.used { fill: #e63946; }
.quad { fill: rgba(230,57,70,.15); stroke: #e63946; stroke-width: 2; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Happy Ending demo: place up to 5 points, then search every group of 4 for one
// that forms a convex quadrilateral (its convex hull has exactly 4 vertices).
// With 5 points in general position, such a group always exists.
const MAX_PTS = 5;
const svg = document.getElementById('canvas');
const NS = 'http://www.w3.org/2000/svg';
let points = []; // the placed points, each {x, y}
let quadEl = null;

// Cross product of (a-o) and (b-o); sign tells left/right turn direction.
function cross(o, a, b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

// Andrew's monotone chain: returns the vertices of the convex hull, in order.
function convexHull(pts) {
  const sorted = [...pts].sort((a, b) => a.x - b.x || a.y - b.y);
  const n = sorted.length;
  if (n < 3) return sorted;
  const lower = [];
  for (const p of sorted) {
    while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0) lower.pop();
    lower.push(p);
  }
  const upper = [];
  for (let i = n - 1; i >= 0; i--) {
    const p = sorted[i];
    while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p) <= 0) upper.pop();
    upper.push(p);
  }
  lower.pop(); upper.pop();
  return lower.concat(upper);
}

// Four points are a convex quadrilateral iff none of them sits inside the triangle of the other three, i.e. the hull of all four keeps all four vertices.
function isConvexQuad(four) {
  return convexHull(four).length === 4;
}

// All C(n,4) subsets of 4 points, checked in order.
function combinations4(pts) {
  const res = [];
  const n = pts.length;
  for (let a = 0; a < n; a++)
    for (let b = a + 1; b < n; b++)
      for (let c = b + 1; c < n; c++)
        for (let d = c + 1; d < n; d++)
          res.push([pts[a], pts[b], pts[c], pts[d]]);
  return res;
}

// Try every 4-subset; return the first one whose hull has 4 vertices.
function findConvexQuad(pts) {
  for (const combo of combinations4(pts)) {
    if (isConvexQuad(combo)) return combo;
  }
  return null;
}

function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function render() {
  svg.innerHTML = '';
  if (quadEl) quadEl = null;
  points.forEach((p, i) => {
    const c = document.createElementNS(NS, 'circle');
    c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 6);
    c.setAttribute('class', 'pt');
    svg.appendChild(c);
  });
}

svg.addEventListener('click', (e) => {
  if (points.length >= MAX_PTS) return;
  const rect = svg.getBoundingClientRect();
  const vb = svg.viewBox.baseVal;
  const x = ((e.clientX - rect.left) / rect.width) * vb.width;
  const y = ((e.clientY - rect.top) / rect.height) * vb.height;
  points.push({ x, y });
  render();
  if (points.length < MAX_PTS) setStatus(fmt('Placed! %n% more to go.', { n: MAX_PTS - points.length }), '');
  else setStatus('Five points placed — press Find the convex quadrilateral.', '');
});

function find() {
  if (points.length < 4) { setStatus('Place at least 4 points first.', 'bad'); return; }
  const quad = findConvexQuad(points);
  if (!quad) { setStatus('No convex quadrilateral found among these points (try adding more).', 'bad'); return; }
  // Re-order the winning 4 points around their hull so the polygon draws without crossing edges.
  const ordered = convexHull(quad);
  const poly = document.createElementNS(NS, 'polygon');
  poly.setAttribute('points', ordered.map(p => p.x + ',' + p.y).join(' '));
  poly.setAttribute('class', 'quad');
  svg.insertBefore(poly, svg.firstChild);
  points.forEach(p => {
    if (quad.includes(p)) {
      const c = document.createElementNS(NS, 'circle');
      c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 6);
      c.setAttribute('class', 'pt used');
      svg.appendChild(c);
    }
  });
  setStatus(fmt('Found it! These %n% points form a convex quadrilateral, highlighted below.', { n: quad.length }), 'ok');
}

document.getElementById('find').addEventListener('click', find);
document.getElementById('reset').addEventListener('click', () => {
  points = []; render(); setStatus('Click to place a point.', '');
});
render();
Result
Console

Drag points around and try again — place them in a cluster, in a near-line, in a star pattern. It doesn't matter how you arrange five points: four of them will always outline a convex quadrilateral. The demo checks every group of four points and stops at the first convex one it finds.

The Real Complexity

The five-point case is solved: any 5 points in general position contain 4 that form a convex quadrilateral, and 4 points are not always enough (place one point inside a triangle formed by the other three and no convex quadrilateral appears). This was settled by Klein, Erdős and Szekeres in the 1930s.

Erdős and Szekeres went further and defined ES(n)ES(n) as the smallest number of points (in general position) that is guaranteed to contain a convex polygon with nn vertices. They proved ES(n)ES(n) is always finite — no matter how large nn is, enough points will always force a convex nn-gon, they just conjectured exactly how many:

ES(n)=2n−2+1ES(n) = 2^{n-2} + 1

  • For n=4n = 4: 22+1=52^{2}+1 = 5 points — proved (the case above).
  • For n=5n = 5: 23+1=92^{3}+1 = 9 points — proved (Erdős and Szekeres themselves, later confirmed exhaustively by computer search).
  • For n=6n = 6: 24+1=172^{4}+1 = 17 points — proved in 2006, via an exhaustive computer-assisted case analysis.
  • For n≥7n \geq 7: open. Nobody has proved or disproved the formula for any larger nn. The best known bounds sandwich ES(n)ES(n) between roughly 2n+o(n)2^{n + o(n)} below and 2n−2+12^{n-2}+1 above — a 2016 breakthrough by Andrew Suk showed the conjecture is "asymptotically almost true," but the exact value for n≥7n \geq 7 remains unknown.

Erdős, true to his habit of attaching cash prizes to open problems, offered $500 for a resolution of the general conjecture — one of many "Erdős prizes" still unclaimed decades after his death. This sits squarely inside Ramsey theory: the idea that any sufficiently large, sufficiently unstructured set of objects must contain some highly structured pattern, whether the objects are points, graphs, or numbers.

Where It Matters

A puzzle about five dots might look like pure recreation, but the same reasoning shows up across mathematics and computing:

  • Computational geometry: algorithms that build a convex hull, triangulate point sets, or detect convex substructures all lean on the same "some subset must be convex" reasoning.
  • Ramsey theory: the Happy Ending problem is one of the founding examples of Ramsey-type results — guarantees that structure is unavoidable once a set is large enough, later generalized far beyond geometry.
  • Extremal combinatorics: pinning down exact thresholds like ES(n)ES(n) is a template for a whole family of "how many objects force this pattern" questions.
  • Robust statistics and pattern recognition: reasoning about which subsets of scattered data points are guaranteed to have a "nice" (convex) shape shows up when outlier-resistant shapes are extracted from noisy geometric data.

Understand why five points can't dodge a convex quadrilateral, and you've touched the same combinatorial machinery that powers geometric algorithms and decades of Ramsey-theoretic research.

Conclusion

Five points always hide a convex quadrilateral — that much has been certain since the 1930s, and the mathematicians who proved it fell in love doing so. But scale the question up, ask about convex hexagons, heptagons, or any nn-gon, and the exact threshold 2n−2+12^{n-2}+1 is only confirmed up to n=6n = 6.

For every larger nn, the precise answer remains open, guarded by an unclaimed $500 prize. It's a rare kind of problem: simple enough to try with a handful of dots on a napkin, and stubborn enough that, decades later, nobody knows exactly where the next convex shape is guaranteed to appear.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/happy-ending-problem/Content licensed under CC BY-NC 4.0.