Davenport-Schinzel Sequences

Introduction

Imagine you have $n$ straight-line segments spread across a canvas. At each x-coordinate, some subset of them is visible; the one sitting lowest at every point forms the lower envelope — a staircase-like curve that traces the minimum height.

You might expect the envelope to have $O(n^{2})$ pieces: after all, $n$ segments can cross each other up to $\binom{n}{2}$ times. But in practice the envelope is almost linear. That surprises even working geometers the first time they see it.

The explanation lives in a combinatorial object called a Davenport-Schinzel sequence. Named after Harold Davenport and Andrzej Schinzel (1965), these sequences encode the alternation pattern of which curve is lowest as you sweep from left to right. The key constraint — no two symbols may alternate more than $s$ times — turns out to be exactly what keeps the envelope tame.

For line segments ( $s = 1$ ) the envelope has at most $2n - 1$ pieces. For curves that cross at most once each pair ( $s = 2$ ) the bound is $\Theta(n\,\alpha(n))$ , where $\alpha$ is the inverse Ackermann function — a quantity that grows so slowly it is effectively a constant for every $n$ you will ever encounter. That near-linear bound has consequences across all of computational geometry.

Build the Lower Envelope

Click anywhere on the canvas to drop endpoints and add a new segment. The lower envelope — the minimum-height visible curve — is redrawn in real time. Watch the segment count and the envelope-piece count side by side.

<!-- toolbar + canvas layout -->
<div class="toolbar">
  <span class="info">Segments: <b id="seg-count">0</b> &nbsp;|&nbsp; Envelope pieces: <b id="env-count">0</b></span>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<p class="hint">Click once to place the first endpoint, click again to complete the segment. Add more segments to see the envelope grow.</p>
<canvas id="cv" width="560" height="320"></canvas>
<div class="status" id="status">Click anywhere to place the first endpoint of a segment.</div>

/* canvas demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.toolbar { display: flex; align-items: center; justify-content: space-between; margin-bottom: .4rem; }
.info { font-size: .9rem; color: #444; }
.hint { font-size: .85rem; color: #555; margin: 0 0 .4rem; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair;
         background: #f8fafc; display: block; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .45rem; color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .85rem; 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] ?? ''));
// Lower-envelope demo: click to place segment endpoints two at a time.
// The bold colored overlay is the lower envelope (minimum-y curve).
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
// list of {x1,y1,x2,y2} ordered left-to-right
const segments = [];
// first endpoint waiting for its pair
let pending = null;
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6a4c93','#f4a261','#264653','#a8dadc'];

// evaluate segment y at a given x (assumes x in [x1,x2])
function segY(seg, x) {
  const t = (x - seg.x1) / (seg.x2 - seg.x1);
  return seg.y1 + t * (seg.y2 - seg.y1);
}

// compute the lower-envelope pieces as {x0,x1,idx} intervals
function computeEnvelope() {
  const W = cv.width;
  // critical x values: endpoints + intersections
  const xs = new Set();
  xs.add(0); xs.add(W);
  segments.forEach(s => { xs.add(s.x1); xs.add(s.x2); });
  // add all pairwise intersection x-coordinates
  for (let i = 0; i < segments.length; i++) {
    for (let j = i + 1; j < segments.length; j++) {
      const xi = intersectX(segments[i], segments[j]);
      if (xi !== null && xi > 0 && xi < W) xs.add(xi);
    }
  }
  const sortedX = [...xs].sort((a, b) => a - b);
  // sweep intervals, track which segment is minimum
  const pieces = [];
  let prevMin = null;
  for (let k = 0; k < sortedX.length - 1; k++) {
    const xMid = (sortedX[k] + sortedX[k + 1]) / 2;
    let minY = Infinity, minIdx = -1;
    segments.forEach((s, i) => {
      if (xMid >= s.x1 && xMid <= s.x2) {
        const y = segY(s, xMid);
        if (y < minY) { minY = y; minIdx = i; }
      }
    });
    if (minIdx !== -1) {
      if (prevMin !== minIdx) {
        pieces.push({ x0: sortedX[k], x1: sortedX[k + 1], idx: minIdx });
        prevMin = minIdx;
      } else {
        pieces[pieces.length - 1].x1 = sortedX[k + 1];
      }
    } else {
      prevMin = null;
    }
  }
  return pieces;
}

// x-coordinate of intersection of two non-vertical lines, or null
function intersectX(a, b) {
  const dya = a.y2 - a.y1, dxa = a.x2 - a.x1;
  const dyb = b.y2 - b.y1, dxb = b.x2 - b.x1;
  if (dxa === 0 || dxb === 0) return null;
  const ma = dya / dxa, mb = dyb / dxb;
  if (Math.abs(ma - mb) < 1e-10) return null;
  const ba = a.y1 - ma * a.x1, bb = b.y1 - mb * b.x1;
  return (bb - ba) / (ma - mb);
}

function draw() {
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  // draw all segments faintly
  segments.forEach((s, i) => {
    ctx.strokeStyle = COLORS[i % COLORS.length];
    ctx.lineWidth = 1.5;
    ctx.globalAlpha = 0.55;
    ctx.beginPath(); ctx.moveTo(s.x1, s.y1); ctx.lineTo(s.x2, s.y2); ctx.stroke();
    ctx.globalAlpha = 1;
    [{ x: s.x1, y: s.y1 }, { x: s.x2, y: s.y2 }].forEach(p => {
      ctx.fillStyle = COLORS[i % COLORS.length];
      ctx.beginPath(); ctx.arc(p.x, p.y, 3.5, 0, 2 * Math.PI); ctx.fill();
    });
  });
  // draw the pending first endpoint
  if (pending) {
    ctx.strokeStyle = '#aaa';
    ctx.setLineDash([4, 3]);
    ctx.lineWidth = 1;
    ctx.beginPath(); ctx.arc(pending.x, pending.y, 4, 0, 2 * Math.PI); ctx.stroke();
    ctx.setLineDash([]);
  }
  // draw the lower envelope thickly
  if (segments.length > 0) {
    const pieces = computeEnvelope();
    ctx.lineWidth = 3;
    ctx.globalAlpha = 0.95;
    pieces.forEach(p => {
      const s = segments[p.idx];
      ctx.strokeStyle = COLORS[p.idx % COLORS.length];
      const y0 = segY(s, p.x0), y1 = segY(s, p.x1);
      ctx.beginPath(); ctx.moveTo(p.x0, y0); ctx.lineTo(p.x1, y1); ctx.stroke();
    });
    ctx.globalAlpha = 1;
    document.getElementById('env-count').textContent = pieces.length;
  } else {
    document.getElementById('env-count').textContent = 0;
  }
  document.getElementById('seg-count').textContent = segments.length;
}

function updateStatus() {
  const n = segments.length;
  if (n === 0) {
    document.getElementById('status').textContent = 'Click anywhere to place the first endpoint of a segment.';
  } else if (pending) {
    document.getElementById('status').textContent = 'Now click a second point to complete the segment.';
  } else {
    const pieces = computeEnvelope().length;
    const worst = n * n;
    document.getElementById('status').textContent =
      fmt('Envelope has %pieces% pieces for %n% segments — naïve worst case would be n² = %worst%.', { pieces: pieces, n: n, worst: worst });
  }
}

cv.addEventListener('click', e => {
  const rect = cv.getBoundingClientRect();
  const scaleX = cv.width / rect.width;
  const scaleY = cv.height / rect.height;
  const x = (e.clientX - rect.left) * scaleX;
  const y = (e.clientY - rect.top) * scaleY;
  if (!pending) {
    pending = { x, y };
  } else {
    if (Math.abs(x - pending.x) > 5) {
      // normalize so x1 <= x2
      const seg = pending.x < x
        ? { x1: pending.x, y1: pending.y, x2: x, y2: y }
        : { x1: x, y1: y, x2: pending.x, y2: pending.y };
      segments.push(seg);
    }
    pending = null;
  }
  draw();
  updateStatus();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  segments.length = 0;
  pending = null;
  draw();
  updateStatus();
});

draw();
updateStatus();

<!-- toolbar + canvas layout -->
<div class="toolbar">
  <span class="info">Segments: <b id="seg-count">0</b> &nbsp;|&nbsp; Envelope pieces: <b id="env-count">0</b></span>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<p class="hint">Click once to place the first endpoint, click again to complete the segment. Add more segments to see the envelope grow.</p>
<canvas id="cv" width="560" height="320"></canvas>
<div class="status" id="status">Click anywhere to place the first endpoint of a segment.</div>

/* canvas demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.toolbar { display: flex; align-items: center; justify-content: space-between; margin-bottom: .4rem; }
.info { font-size: .9rem; color: #444; }
.hint { font-size: .85rem; color: #555; margin: 0 0 .4rem; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair;
         background: #f8fafc; display: block; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .45rem; color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .85rem; 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] ?? ''));
// Lower-envelope demo: click to place segment endpoints two at a time.
// The bold colored overlay is the lower envelope (minimum-y curve).
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
// list of {x1,y1,x2,y2} ordered left-to-right
const segments = [];
// first endpoint waiting for its pair
let pending = null;
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6a4c93','#f4a261','#264653','#a8dadc'];

// evaluate segment y at a given x (assumes x in [x1,x2])
function segY(seg, x) {
  const t = (x - seg.x1) / (seg.x2 - seg.x1);
  return seg.y1 + t * (seg.y2 - seg.y1);
}

// compute the lower-envelope pieces as {x0,x1,idx} intervals
function computeEnvelope() {
  const W = cv.width;
  // critical x values: endpoints + intersections
  const xs = new Set();
  xs.add(0); xs.add(W);
  segments.forEach(s => { xs.add(s.x1); xs.add(s.x2); });
  // add all pairwise intersection x-coordinates
  for (let i = 0; i < segments.length; i++) {
    for (let j = i + 1; j < segments.length; j++) {
      const xi = intersectX(segments[i], segments[j]);
      if (xi !== null && xi > 0 && xi < W) xs.add(xi);
    }
  }
  const sortedX = [...xs].sort((a, b) => a - b);
  // sweep intervals, track which segment is minimum
  const pieces = [];
  let prevMin = null;
  for (let k = 0; k < sortedX.length - 1; k++) {
    const xMid = (sortedX[k] + sortedX[k + 1]) / 2;
    let minY = Infinity, minIdx = -1;
    segments.forEach((s, i) => {
      if (xMid >= s.x1 && xMid <= s.x2) {
        const y = segY(s, xMid);
        if (y < minY) { minY = y; minIdx = i; }
      }
    });
    if (minIdx !== -1) {
      if (prevMin !== minIdx) {
        pieces.push({ x0: sortedX[k], x1: sortedX[k + 1], idx: minIdx });
        prevMin = minIdx;
      } else {
        pieces[pieces.length - 1].x1 = sortedX[k + 1];
      }
    } else {
      prevMin = null;
    }
  }
  return pieces;
}

// x-coordinate of intersection of two non-vertical lines, or null
function intersectX(a, b) {
  const dya = a.y2 - a.y1, dxa = a.x2 - a.x1;
  const dyb = b.y2 - b.y1, dxb = b.x2 - b.x1;
  if (dxa === 0 || dxb === 0) return null;
  const ma = dya / dxa, mb = dyb / dxb;
  if (Math.abs(ma - mb) < 1e-10) return null;
  const ba = a.y1 - ma * a.x1, bb = b.y1 - mb * b.x1;
  return (bb - ba) / (ma - mb);
}

function draw() {
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  // draw all segments faintly
  segments.forEach((s, i) => {
    ctx.strokeStyle = COLORS[i % COLORS.length];
    ctx.lineWidth = 1.5;
    ctx.globalAlpha = 0.55;
    ctx.beginPath(); ctx.moveTo(s.x1, s.y1); ctx.lineTo(s.x2, s.y2); ctx.stroke();
    ctx.globalAlpha = 1;
    [{ x: s.x1, y: s.y1 }, { x: s.x2, y: s.y2 }].forEach(p => {
      ctx.fillStyle = COLORS[i % COLORS.length];
      ctx.beginPath(); ctx.arc(p.x, p.y, 3.5, 0, 2 * Math.PI); ctx.fill();
    });
  });
  // draw the pending first endpoint
  if (pending) {
    ctx.strokeStyle = '#aaa';
    ctx.setLineDash([4, 3]);
    ctx.lineWidth = 1;
    ctx.beginPath(); ctx.arc(pending.x, pending.y, 4, 0, 2 * Math.PI); ctx.stroke();
    ctx.setLineDash([]);
  }
  // draw the lower envelope thickly
  if (segments.length > 0) {
    const pieces = computeEnvelope();
    ctx.lineWidth = 3;
    ctx.globalAlpha = 0.95;
    pieces.forEach(p => {
      const s = segments[p.idx];
      ctx.strokeStyle = COLORS[p.idx % COLORS.length];
      const y0 = segY(s, p.x0), y1 = segY(s, p.x1);
      ctx.beginPath(); ctx.moveTo(p.x0, y0); ctx.lineTo(p.x1, y1); ctx.stroke();
    });
    ctx.globalAlpha = 1;
    document.getElementById('env-count').textContent = pieces.length;
  } else {
    document.getElementById('env-count').textContent = 0;
  }
  document.getElementById('seg-count').textContent = segments.length;
}

function updateStatus() {
  const n = segments.length;
  if (n === 0) {
    document.getElementById('status').textContent = 'Click anywhere to place the first endpoint of a segment.';
  } else if (pending) {
    document.getElementById('status').textContent = 'Now click a second point to complete the segment.';
  } else {
    const pieces = computeEnvelope().length;
    const worst = n * n;
    document.getElementById('status').textContent =
      fmt('Envelope has %pieces% pieces for %n% segments — naïve worst case would be n² = %worst%.', { pieces: pieces, n: n, worst: worst });
  }
}

cv.addEventListener('click', e => {
  const rect = cv.getBoundingClientRect();
  const scaleX = cv.width / rect.width;
  const scaleY = cv.height / rect.height;
  const x = (e.clientX - rect.left) * scaleX;
  const y = (e.clientY - rect.top) * scaleY;
  if (!pending) {
    pending = { x, y };
  } else {
    if (Math.abs(x - pending.x) > 5) {
      // normalize so x1 <= x2
      const seg = pending.x < x
        ? { x1: pending.x, y1: pending.y, x2: x, y2: y }
        : { x1: x, y1: y, x2: pending.x, y2: pending.y };
      segments.push(seg);
    }
    pending = null;
  }
  draw();
  updateStatus();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  segments.length = 0;
  pending = null;
  draw();
  updateStatus();
});

draw();
updateStatus();

Result

Console

Notice that even with many segments the envelope piece count grows much more slowly than $n^{2}$ . For line segments specifically, the bound is $2n - 1$ : once a segment loses the minimum to another it never reclaims it, so each segment contributes at most two pieces. That is the simplest Davenport-Schinzel bound ( $s = 1$ ) in action.

The Real Complexity

Let $\lambda_{s}(n)$ denote the maximum length of a Davenport-Schinzel sequence of order $s$ on $n$ symbols. The bounds are solved — worked out by Micha Sharir and Pankaj Agarwal through the late 1980s and 1990s:

Order $s$	Curve type	$\lambda_{s}(n)$ bound
1	no crossings	$2n - 1$
2	$\leq 1$ crossing per pair	$\Theta(n\,\alpha(n))$
3	$\leq 2$ crossings per pair	$\Theta(n \cdot 2^{\alpha(n)})$
even $s \geq 4$	$\leq s-1$ crossings	$\Theta(n \cdot \alpha(n)^{O(1)})$
odd $s \geq 5$	$\leq s-1$ crossings	$\Theta(n \cdot 2^{\alpha(n)^{O(1)}})$

The inverse Ackermann function $\alpha(n)$ is defined as the inverse of the Ackermann function $A(k,k)$ : the smallest $k$ such that $A(k,k) \geq n$ . It grows so slowly that $\alpha(n) \leq 4$ for every $n$ smaller than a power-tower of twos of height $65536$ . In all practical terms, $\lambda_{2}(n) = O(n)$ .

The key insight behind all these bounds is an alternation argument: if symbol $a$ and symbol $b$ both appear after one another more than $s$ times in the sequence, you can derive a contradiction with the crossing number constraint. Counting these forbidden alternations leads to recurrences that the Ackermann function resolves.

The result is one of the rare theorems where the answer is genuinely super-linear but barely so — a tiny gap that took decades of combinatorics to pin down precisely.

Where It Matters

The near-linear complexity of the lower envelope — guaranteed by Davenport-Schinzel bounds — unlocks efficient algorithms across geometry:

Motion planning: a robot arm avoiding obstacles traces a path in configuration space that is essentially a lower envelope. Near-linear complexity means near-linear planning.
Voronoi diagrams: the Voronoi diagram of $n$ sites is dual to the lower envelope of $n$ cones. The $O(n)$ envelope directly gives the $O(n)$ complexity of 2-D Voronoi diagrams.
Hidden-surface removal: deciding which of $n$ triangles is visible from a viewpoint reduces to envelope queries. Near-linear bounds keep rendering algorithms tractable.
Range searching: many divide-and-conquer range-tree structures rely on the fact that dual lower envelopes are nearly linear to bound their query time.
Kinetic data structures: tracking the minimum among $n$ linearly-moving values uses exactly the $s=1$ DS bound — the minimum changes $O(n)$ times total.

Davenport-Schinzel sequences appear whenever a sweep encounters "which curve is current minimum" — a pattern so common in computational geometry that the sequences are considered a core tool of the field. See also convex hull and closest pair for other canonical geometry problems.

Conclusion

Davenport-Schinzel sequences reveal a beautiful surprise: $n$ curves, each crossing any other at most $s$ times, can only produce an envelope of nearly linear complexity. The forbidden alternation rule does the heavy lifting, and the inverse Ackermann function is the price of rigor.

That price is tiny — $\alpha(n) \leq 4$ in practice — yet it took decades to prove it was there at all. The result transformed computational geometry, turning problems that naively require $O(n^{2})$ time into algorithms that run in $O(n \log n)$ or even $O(n\,\alpha(n))$ .

The next time you see a clean $O(n \log n)$ bound for a geometry problem, there is a good chance a Davenport-Schinzel argument is hiding underneath it, quietly holding the envelope together.

Comments

Loading comments...

https://www.kipuhub.com/en/article/davenport-schinzel/Content licensed under CC BY-NC 4.0.

Cookies & privacy

When n curves make an almost-linear envelope