Máxima in één lange lijn

Probeer maar eens onder strenge wiskundige beperkingen een zo goed mogelijke tekening te maken.

Knijp je ogen half dicht en kijk van een afstandje naar de afgebeelde lijntekening: Máxima doemt op. De tekening is gemaakt door wiskundige Robert Bosch en informaticus Tom Wexler, beiden verbonden aan Oberlin College in de Amerikaanse staat Ohio.

Deze interessante tekening is óók een wiskundig hoogstandje. Het uitgangspunt van de tekening is een rooster van 31 × 45 punten. Al deze 1395 punten zijn via een zogeheten Hamiltoncircuit met elkaar verbonden. Zo’n circuit, vernoemd naar de Ierse wiskundige William Rowan Hamilton (1805-1865), is een rondwandeling langs alle punten waarbij elk punt precies één keer wordt aangedaan. De tekening bestaat dus uit één lange lijn.

Bosch en Wexler legden zich om esthetische redenen nog de volgende spelregel op. Twee punten mogen met elkaar worden verbonden als ze, in schaakjargon, een ‘koningszet’ of een ‘paardensprong’ van elkaar vandaan liggen.

Tijdens Bridges 2015, een congres over wiskunde, muziek, kunst, architectuur en cultuur dat van 29 juli tot 2 augustus plaatsvindt aan de universiteit van Baltimore, spreekt Bosch over de wiskunde achter zijn figuratieve Hamiltoncircuits. De tekening van Máxima maakte hij speciaal voor deze krant. „Een optimaal portret voor op optimalisatie gebaseerde kunst,” aldus Bosch.

Een getalwaarde tussen 0 en 1, afhankelijk van hoe donker of licht het er is

Bosch en Wexler noemen het probleem waarbij een beeld volgens de spelregels optimaal wordt omgezet in een Hamiltoncircuit het Figurative Tour Problem (FTP). Om het probleem te kwantificeren, geven ze elk 1 × 1-vierkantje waarvan de hoekpunten roosterpunten zijn, een getalwaarde tussen 0 en 1, afhankelijk van hoe donker of licht het originele plaatje (omgezet in grijswaarden) in dat gebiedje is. Zo is de helderheid van elk vierkantje gedefinieerd en kan voor elk vierkantje worden vastgesteld hoeveel inkt het idealiter moet bevatten.

Met behulp van een computerprogramma dat diverse wiskundige programmeringsproblemen kan oplossen, zoeken de FTP-onderzoekers vervolgens naar een Hamiltoncircuit waarbij het totale verschil in helderheid tussen het oorspronkelijke beeld en de lijntekening minimaal is.

Bosch en Wexler vermoeden dat het Máxima-circuit ‘bijna’ optimaal is. Om de oplossing te vinden die honderd procent optimaal is, zouden ze hun computer veel langer moeten laten rekenen, vanwege de complexiteit van het probleem.

FTP kan worden geformuleerd als beslissingsprobleem, een vraag waarop het antwoord ja of nee is: gegeven een afbeelding (A), een rooster waarop A volgens de spelregels moet worden gevisualiseerd en een getal (c); bestaat er een Hamiltoncircuit waarbij de som van de verschillen in helderheid kleiner is dan c?

FTP vertoont sterke gelijkenis met het beroemde Handelsreizigersprobleem, waarbij het draait om de vraag hoe je zo voordelig mogelijk een rondreis kan maken langs een aantal steden met als voorwaarde dat ze alle eenmaal worden aangedaan. Een efficiënt algoritme om het Handelsreizigersprobleem op te lossen is nog nooit gevonden.