A fractal shortcut for the travelling salesman: ordering stops along a Hilbert curve

AI HLAA HL Ambitious Also in: Networks & graphs, Optimisation

Research question

If delivery stops are visited in the order they appear along a Hilbert space-filling curve, how long is the route compared with the nearest-neighbour route and a lower bound, for real sets of stops?

Adapt it: change the place, the data or the comparison until the question is yours.

Free: the A–E checklist an examiner uses, by email ↓

Why it makes a good exploration

Space-filling curves are a genuine fast heuristic for routing. Comparing them with graph-theory methods links fractals to an applied decision.

The mathematics you'll need

Constructing the Hilbert curve recursively
Mapping a point to its position along the curve
Route length calculations
Nearest-neighbour and lower-bound methods (AI HL)
Comparing ratios over many sets of stops

Course labels show where a technique sits; using maths from outside your course is fine if you explain it clearly and say it is new to you.

Where the data comes from

Take addresses or landmarks from OpenStreetMap as stops; generate random sets for comparison.

OpenStreetMap — Free map with exact coordinates of schools, hospitals, shops and stations; export or read off coordinates.
GeoGebra — Free geometry and graphing software — Voronoi diagrams, loci and regression built in.

Cite every source in a footnote where you use it and in your bibliography. Check the licence of any dataset you download.

A possible outline

Explain the curve's construction.
Order stops along it and find the route length.
Compare with nearest neighbour and a lower bound.
Repeat for many sets of stops.
Reflect on roads versus straight lines.

Pitfalls that cost marks

Not explaining how a point's position on the curve is found.
Comparing on one example only.
Ignoring road distances in the conclusion.

Showing personal engagement

Use your own delivery round or paper route.
Predict which method wins before testing.
Try a different space-filling curve.

See Criterion C: personal engagement for what examiners look for.

Which course is it for?

Course	Fit	Maths to lean on
AA SL	Not a natural fit	The core technique sits in the AI course or at HL; an AA SL student could use it only as clearly explained new mathematics.
AA HL	Good fit	Constructing the Hilbert curve recursively; Mapping a point to its position along the curve
AI SL	Not a natural fit	The mathematics is mainly AA or HL (calculus or proof beyond AI SL); an AI SL version would need a data-driven, technology-based approach.
AI HL	Good fit	Constructing the Hilbert curve recursively; Mapping a point to its position along the curve

Level: Ambitious. Suits confident students; expect to learn some mathematics on your own. See how the IA differs between AA and AI, SL and HL.

How this idea reaches the top bands

Personal engagement (C)

Generate the fractal or the iteration yourself, choose your own variation (a different rule, angle or starting value), and pursue a question you raised while exploring.

Reflection (D)

Reflect on the limits of the model: real coastlines and plants are only self-similar over a range of scales, and computer iterations carry rounding error. Say how that affects your numbers. For this idea, start with: not explaining how a point's position on the curve is found — say how it affects your answer.

Use of mathematics (E)

SL: Geometric sequences and series for lengths and areas, logarithms for dimension, and iteration of functions, each calculated and checked numerically.

HL: Proof of a limit or dimension, complex-number iteration with a derived condition, or analysis of fixed points and their stability using derivatives.

Criteria A and B (presentation and communication) work the same way for every idea: see the guides to Criterion A and Criterion B.

Taking it further

Prove a bound on how much longer the curve route can be in the worst case, or compare different curve orders.

Extending it for HL

This idea already has HL mathematics in it: Nearest-neighbour and lower-bound methods. Find fixed points and decide their stability with derivatives, or prove the limit you found numerically.

See a complete IA, marked

Our annotated exemplar What is the quickest way to deliver a leaflet to every house on my estate? (AI HL) asks a different question, but shows how a complete fractals & chaos exploration is structured and marked, with an examiner's comment on every criterion. Free excerpts and the full marking table are on its page.

Before you start: the checklist an examiner uses

Every check for Criteria A–E in a 4-page PDF, the mistakes that cost the most marks and a self-assessment grid. We'll email it with a short IA tip every few days, timed to your deadline if you give it. Free — no account, no payment.

Get the free checklist

Turn this idea into your IA

Plan this IAOpens the planner with this question, the maths and data sources filled in. Criteria checklistCheck your plan or draft against the A–E descriptors and self-grade before you hand it in. AI feedback on a draftCriterion-by-criterion feedback with evidence from your own text. Coaching, not rewriting. Examiner reviewPete, an IB examiner, reads your draft and talks it through with you (€100).