Malfatti Circles: hoe je zo min mogelijk marmer verspilt

Malfatti beschrijft het motief voor deze technische taak aan het begin van zijn in 1803 gepubliceerde tekst. Stel dat je een rechthoekig prisma hebt, bijvoorbeeld gemaakt van marmer, en je wilt er drie ronde cilinders uit snijden zodat zo min mogelijk materiaal mogelijke overblijfselen: hoe zijn deze cilinders gerangschikt en wat zijn hun stralen? Dit driedimensionale probleem kan natuurlijk gemakkelijk in twee dimensies worden vertaald, en Malfatti dacht dat zijn constructie, gegeven door de drie formules, het antwoord zou zijn.

Op het eerste gezicht lijkt dit volkomen redelijk. Je moet beter kijken om te zien dat er betere oplossingen zijn. Als we ons bijvoorbeeld een zeer lange, smalle en rechthoekige driehoek voorstellen, dan moeten we volgens Malfatti twee kleine cirkels tekenen die op elkaar zijn gestapeld aan het brede uiteinde van de driehoek en een grotere cirkel ernaast die de twee kleinere raakt degenen. In plaats daarvan kunnen we gewoon beginnen met het tekenen van de ingeschreven cirkel die het brede uiteinde van de driehoek vult, vervolgens een iets kleinere cirkel ernaast en een kleinere cirkel naast de tweede. Dan voldoen ze niet meer aan de voorwaarden van Malfatti, maar bestrijken ze duidelijk een groter gebied dan de driehoek.

Het hebzuchtige algoritme biedt de oplossing

Dit werd wiskundig bewezen in de jaren ’30 – verbazingwekkend genoeg duurde het meer dan 100 jaar. Nog verrassender is het bewijs uit 1967 van Michael GoldbergDe cirkels van Malfatti kunnen nooit perfect zijn, maar er zijn er altijd nog drie die meer terrein beslaan. U kunt de best mogelijke oplossing krijgen met een bestand “hebzuchtig algoritme” vinden: Zoek eerst de cirkel die het grootst mogelijke gebied in de driehoek beslaat. Vervolgens wordt de cirkel bepaald die de meeste ruimte in de resterende gebieden kan innemen; De derde cirkel wordt op dezelfde manier bepaald. Zo vind je altijd de perfecte oplossing, tenminste als je maar drie circuits gebruikt. Of dit hebzuchtige algoritme ook voor vier of meer circuits de optimale oplossing kan vinden, is twijfelachtig maar niet bewezen.