The minimum length of an axis-aligned rectangular tiling of a flat torus

Dit artikel bepaalt de minimale som van de omtrekken voor een as-uitgelijnde rechthoekige betegeling van een platte torus en bewijst dat dit minimum wordt bereikt door precies één of twee rechthoeken.

De kern

Stel je voor dat je een videospelletje speelt, zoals Pac-Man of een oude arcade-game. In die spellen loop je vaak van de ene kant van het scherm naar de andere, en als je de rechterkant verlaat, verschijn je plotseling weer aan de linkerkant. Hetzelfde geldt voor boven en onder.

Wiskundigen noemen zo'n oppervlak een vlakke torus. Het klinkt als een ingewikkeld woord voor een donut, maar in dit geval is het een platte, oneindige kaart die "op zichzelf" is gesloten.

De auteurs van dit paper (Hau-Yi Lin, Wu-Hsiung Lin en Gerard Chang) hebben een probleem opgelost dat lijkt op het inrichten van een kamer, maar dan op zo'n donut-oppervlak.

Het Probleem: De Perfecte Tegelvloer

Stel je voor dat je deze donut-vloer wilt betegelen met rechthoekige tegels. Maar er zijn twee regels:

1. De tegels moeten perfect rechtop staan (hun zijkanten lopen precies horizontaal en verticaal, net als op een raster).
2. Je wilt zo min mogelijk randen gebruiken.

Waarom? Omdat elke rand die je legt, "geld" kost (of in dit geval, lengte). Als je een kamer betegelt, wil je niet dat je 100 kleine tegels gebruikt met honderden voeglijnen. Je wilt de minste lijnen mogelijk.

De vraag is: Wat is de kortste totale lengte van lijnen die je nodig hebt om deze donut-vloer volledig te bedekken met rechthoeken?

De Oplossing: Minder is Meer

De onderzoekers hebben ontdekt dat je voor de "goedkoopste" oplossing eigenlijk maar twee opties hebt. Je hoeft niet te denken aan ingewikkelde patronen met tientallen tegels. De beste oplossing bestaat altijd uit:

1. Precies één grote tegel:
   Soms kun je de hele donut-vloer bedekken met één enkele, reusachtige rechthoek. Dit is als het leggen van één groot tapijt dat precies past.

   • Wanneer werkt dit? Alleen als de "donut" een heel specifiek, rechtlijnig patroon heeft.

2. Precies twee tegels:
   Als één grote tegel niet past, dan is de beste oplossing altijd om de vloer te verdelen in twee rechthoeken. Denk aan het verdelen van een kamer in een slaapkamer en een woonkamer met één wand.

   • Wanneer werkt dit? Als de donut een beetje "scheef" is, maar nog steeds een symmetrisch patroon volgt.

De Wiskundige "Magie" (in simpele taal)

Hoe weten ze dit? Ze gebruiken een slimme truc met een meetkundig principe dat al eeuwen bekend is (het stelling van Minkowski), maar dan toegepast op deze specifieke vorm.

Stel je voor dat je een net (een rooster) over de donut legt. De onderzoekers kijken naar de "kortste weg" die je kunt lopen in dat net zonder de regels te breken. Ze bewijzen dat:

• Als je probeert de vloer met drie of meer tegels te leggen, je altijd meer lijnen (randen) nodig hebt dan met één of twee.
• Het is alsof je probeert een pakje in te pakken: soms is één groot stuk papier het snelst, en soms moet je het in tweeën vouwen, maar drie stukken papier is altijd onnodig veel werk.

Waarom is dit belangrijk?

Je denkt misschien: "Wie heeft er nou een donut-vloer?"
Maar dit probleem is heel belangrijk voor:

• Chipontwerp (VLSI): Als je een computerchip ontwerpt, moet je de verschillende onderdelen (logische blokken) op een klein vlak passen. Soms moet je de chip "rondom" laten werken (zoals in de video-game). Het minimaliseren van de lijnen betekent minder materiaal en snellere stroom.
• Kaarten en Netwerken: Het helpt bij het begrijpen van hoe we netwerken kunnen bouwen die efficiënt zijn, zelfs als ze geen begin en eind hebben.

Samenvatting in één zin

De auteurs hebben bewezen dat als je een platte, donut-vormige wereld wilt bedekken met rechthoekige tegels die recht staan, je nooit meer dan twee tegels nodig hebt om de minste hoeveelheid "lijnen" te gebruiken; alles wat ingewikkelder is, is gewoon verspilling.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "The minimum length of an axis-aligned rectangular tiling of a flat torus" in het Nederlands.

Titel: De minimale lengte van een as-georiënteerde rechthoekige tegelindeling van een platte torus

Auteurs: Hau-Yi Lin, Wu-Hsiung Lin, en Gerard Jennhwa Chang.
Publicatie: arXiv:2603.04765v1 [math.CO], 5 maart 2026.

---

1. Probleemstelling

Het artikel behandelt een optimalisatieprobleem binnen de discrete meetkunde en de meetkundige grafentheorie. De kernvraag is: wat is de minimale som van de omtrek (of equivalent, de minimale totale lengte van de lijnsegmenten die de scheidingen vormen) voor een partitionering van een platte torus ($T^2 = \mathbb{R}^2/\Lambda$) in een eindig aantal as-georiënteerde rechthoeken?

• Context: Een platte torus wordt gedefinieerd als het quotiënt van het Euclidische vlak $\mathbb{R}^2$ over een rooster $\Lambda$ gegenereerd door een basis $\{u, v\}$.
• Beperking: De rechthoeken moeten "as-georiënteerd" zijn, wat betekent dat hun zijden parallel lopen aan de coördinaatassen van het vlak.
• Doel: Een gesloten formule vinden voor deze minimale lengte $m(\Lambda)$ en bewijzen dat deze bereikt kan worden door een tegelindeling met precies één of precies twee rechthoeken.

Dit probleem heeft toepassingen in VLSI-vloerplanning (chipontwerp), het tekenen van orthogonale grafen en het bestuderen van de structuur van rechthoekige onderverdelingen (rectangulations).

2. Methodologie en Voorbereiding

De auteurs gebruiken een combinatie van roosterteorie, convex meetkunde en grafentheoretische argumenten.

• Definities:

  • Rooster $\Lambda$: Gedefinieerd door een basis $\{u, v\}$. Het co-volume $d(\Lambda)$ is de oppervlakte van de door de basis opgespannen parallellogram.
  • Lengte $m(T)$: De som van de lengtes van alle randen in het skelet (het graaf) van de tegelindeling $T$. Omdat elke rand twee rechthoeken scheidt of tot één rechthoek behoort, is $m(T)$ gelijk aan de helft van de som van de omtreken van alle rechthoeken.
  • $L_1$-norm: $\|u\|_1 = |x| + |y|$ voor een vector $u=(x,y)$.
  • Kwadranten: $Q_1$ (waar $xy \geq 0$) en $Q_2$ (waar $xy < 0$).

• Belangrijke Stellingen:

  • Minkowski's Convex Body Theorema: Gebruikt om te garanderen dat een convex, centraal symmetrisch gebied met voldoende volume een niet-nul roosterpunt bevat.
  • Kwadrant-basis (Lemma 2.2): Bewezen dat er altijd een basis $\{u, v\}$ bestaat voor $\Lambda$ waarbij $u$ het punt met de minimale $L_1$-norm is in $Q_1 \setminus \{0\}$ en $v$ het punt met de minimale $L_1$-norm in $Q_2$. Deze basis wordt een kwadrant-basis genoemd.

3. Sleutelresultaten en Bijdragen

De auteurs leiden een ondergrens af voor de lengte en bewijzen dat deze ondergrens scherp is (d.w.z. bereikbaar).

A. Ondergrenzen

De minimale lengte wordt bepaald door het minimum van drie mogelijke waarden, afhankelijk van de structuur van het rooster en de aanwezigheid van cycli in het skelet van de tegelindeling:

1. Geval 1: Horizontale of verticale cycli.
   Als het skelet van de tegelindeling een horizontale cyclus bevat, moet de lengte minstens $m_x(\Lambda)$ zijn. Als er een verticale cyclus is, moet de lengte minstens $m_y(\Lambda)$ zijn.

   • $m_x(\Lambda) = d_x + \frac{d(\Lambda)}{d_x}$, waarbij $d_x$ de kleinste positieve $x$-coördinaat is van een punt in $\Lambda$ (indien bestaand).
   • $m_y(\Lambda)$ is analoog gedefinieerd voor de $y$-as.
   • Als er geen dergelijke punten bestaan, zijn deze waarden oneindig.

2. Geval 2: Geen horizontale of verticale cycli.
   Als het skelet geen cycli bevat, bewijzen de auteurs (via Lemma 4.2 en Propositie 4.3) dat de lengte minstens de som van de $L_1$-normen van de kwadrant-basis moet zijn:
   $$m(T) \geq \|u\|_1 + \|v\|_1$$
   Dit wordt bewezen door de structuur van de paden in het skelet te analyseren en vectoren te construeren die in het rooster liggen.

B. De Hoofdstelling (Theorema 5.1)

De minimale lengte $m(\Lambda)$ voor een as-georiënteerde rechthoekige tegelindeling van een platte torus wordt gegeven door:
$$m(\Lambda) = \min \{ \|u\|_1 + \|v\|_1, \ m_x(\Lambda), \ m_y(\Lambda) \}$$
waarbij $\{u, v\}$ een kwadrant-basis van $\Lambda$ is.

C. Constructie van de Optimaal Tegelindeling

Het artikel bewijst niet alleen de ondergrens, maar construeert ook expliciet de tegelindelingen die deze minimumwaarde bereiken:

• Eén rechthoek: Als $m_x(\Lambda)$ of $m_y(\Lambda)$ de minimale waarde is, kan de torus worden gepartitioneerd in precies één rechthoek.
• Twee rechthoeken: Als $\|u\|_1 + \|v\|_1$ de minimale waarde is (en kleiner is dan $m_x$ en $m_y$), kan de torus worden gepartitioneerd in precies twee rechthoeken. De auteurs geven een expliciete constructie voor deze twee rechthoeken gebaseerd op de projecties van de basisvectoren.

4. Significatie en Toepassingen

• Combinatorische Meetkunde: Het artikel levert een volledig antwoord op een fundamenteel optimalisatieprobleem voor rechthoekige onderverdelingen op een torus, een topologie die vaak wordt verwaarloosd ten gunste van het vlak of de bol.
• VLSI en Chipontwerp: In Very Large Scale Integration (VLSI) worden vloerplannen vaak gemodelleerd als rechthoekige onderverdelingen. Het minimaliseren van de totale lengte van de grenzen (interconnecties) is cruciaal voor het verminderen van signaalvertraging en oppervlaktegebruik. De resultaten bieden theoretische limieten voor het ontwerp van dergelijke layouts op periodieke structuren.
• Grafentheorie: De resultaten hebben implicaties voor het tekenen van orthogonale grafen en het vinden van "rectangular duals" (rechthoekige duale grafen) van planaire grafen, maar dan uitgebreid naar toroidale grafen.
• Berekenbaarheid: De auteurs geven in Sectie 6 algoritmen om de waarden $m_x(\Lambda)$, $m_y(\Lambda)$ en de kwadrant-basis efficiënt te berekenen met behulp van de Euclidische algoritme en het doorzoeken van roosterpunten binnen een bepaald straal.

Conclusie

De auteurs hebben een gesloten formule afgeleid voor de minimale totale lengte van de randen in een as-georiënteerde rechthoekige tegelindeling van een platte torus. Ze bewijzen dat de optimale oplossing altijd wordt bereikt door een zeer eenvoudige configuratie: ofwel één enkele rechthoek, ofwel twee rechthoeken. Dit resultaat verenigt concepten uit roosterteorie, convex meetkunde en grafentheorie en biedt een fundamentele basis voor verdere onderzoek naar optimalisatieproblemen op niet-triviale oppervlakken.