Problem 395 asks for the area of the axis-aligned bounding box that contains the entire infinite Pythagorean tree. The local C++, Python, and Java solutions do not enumerate squares to a fixed depth. Instead they model the tree as a self-similar set \(K \subset \mathbb{R}^2\), answer four support-function extremal queries, and finally obtain the numerical area \(28.2453753155\).
In the C++ checkpoint code, a square is represented by a start point \(p\) and a base vector \(z\). Its four corners are
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
where \(i(x,y)=(-y,x)\) is a quarter-turn. The two child squares are obtained by multiplying the base vector by the complex-like constants
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
These have lengths \(|a|=\frac{4}{5}\) and \(|b|=\frac{3}{5}\), so each recursive step both rotates and shrinks. For the root square \(S=[0,1]^2\), the child translations used by the solver are
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
If \(M_c\) denotes the linear map corresponding to complex multiplication by \(c=(u,v)\), then
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
With \(A=M_a\) and \(B=M_b\), the entire infinite tree is the unique compact set satisfying the affine fixed-point equation
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
For any direction \(d\in\mathbb{R}^2\), define the support function
$$h(d)=\sup_{x\in K} d\cdot x.$$
Two standard identities turn the set equation into a scalar recurrence:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
Therefore the exact support value satisfies
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
The helper support_unit_square is exact because the unit square has vertices \((0,0)\), \((1,0)\), \((0,1)\), and \((1,1)\), so
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
The transpose action implemented by apply_transpose_mul is
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
The heap search needs an upper bound for any unfinished subtree. The solver uses the global radial bound \(R=5\), and this follows directly from the same self-similar equation. If every point of \(K\) satisfies \(\|x\|\le R\), then the root square contributes at most \(\sqrt{2}\), the left subtree contributes at most \(1+\frac{4R}{5}\), and the right subtree contributes at most \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\). So it is enough that
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right).$$
This reduces to \(R\ge 5\) and \(R\ge \frac{\sqrt{65}}{2}\), hence \(R=5\) is safe. For any affine copy \(u+M K\), we then obtain the upper bound
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
After a finite child word \(w\), the program stores precisely the pair \(\text{offset}=d\cdot u_w\) and \(\text{dir}=M_w^{\mathsf{T}}d\). The exact contribution is \(\text{offset}+h(\text{dir})\), the lower bound is \(\text{offset}+h_S(\text{dir})\), and the upper bound is \(\text{offset}+\|\text{dir}\|R\). The priority queue always expands the node with the largest upper bound first. Nodes with upper bound at most best + tol are discarded, and because each child multiplies the direction norm by \(\frac{4}{5}\) or \(\frac{3}{5}\), promising bounds decay geometrically.
Once support values are available, the axis-aligned box comes from the four coordinate directions:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
Evaluating the local solver gives
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
so the final area is
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
Before solving the infinite problem, the C++ file verifies the first generation exactly. The left child has corners \((0,1)\), \((\frac{16}{25},\frac{37}{25})\), \((-\frac{12}{25},\frac{41}{25})\), and \((\frac{4}{25},\frac{53}{25})\). The right child has corners \((\frac{16}{25},\frac{37}{25})\), \((1,1)\), \((\frac{28}{25},\frac{46}{25})\), and \((\frac{37}{25},\frac{34}{25})\). Together with the root square, this gives the exact depth-1 box
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
which is exactly what finite_depth_bbox(1) checks.
SupportSolver stores the constants \(a\), \(b\), \(t_1\), and \(t_2\). The function apply_transpose_mul computes \(M_c^{\mathsf{T}}d\), support_unit_square evaluates the base square exactly, and the heap stores triples \((\text{upper\_bound},\text{offset},\text{dir})\). The C++ version uses long double, checks the depth-1 geometry, and also verifies the support fixed-point identity in the four cardinal directions. The Python and Java versions implement the same best-first search with the same constants, but without the extra checkpoint harness.
If one support query expands \(N_d\) nodes, the heap operations cost \(O(N_d\log N_d)\) time and \(O(N_d)\) memory. The final area requires four such queries, so the overall cost is the same order up to a factor of four. This is very different from naive depth-\(n\) generation, which touches \(2^n\) squares and still only approximates the infinite tree. Here the search is adaptive: entire subtrees are pruned as soon as their best possible upper bound cannot beat the current optimum.
Bei Problem 395 wird die Fläche der achsenparallelen Bounding-Box gesucht, die den gesamten unendlichen pythagoreischen Baum enthält. Die lokalen C++-, Python- und Java-Lösungen erzeugen die Quadrate nicht bis zu einer festen Tiefe, sondern modellieren den Baum als selbstähnliche Menge \(K \subset \mathbb{R}^2\), berechnen vier Stützfunktions-Extremwerte und erhalten so die numerische Fläche \(28.2453753155\).
Im C++-Checkpoint wird ein Quadrat durch einen Startpunkt \(p\) und einen Basisvektor \(z\) beschrieben. Seine vier Ecken sind
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
wobei \(i(x,y)=(-y,x)\) eine Drehung um \(90^\circ\) bezeichnet. Die beiden Kinderquadrate entstehen durch Multiplikation des Basisvektors mit den komplexartigen Konstanten
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
Deren Beträge sind \(|a|=\frac{4}{5}\) und \(|b|=\frac{3}{5}\); jeder Rekursionsschritt rotiert also und verkleinert zugleich. Für das Wurzelquadrat \(S=[0,1]^2\) verwendet der Solver die Verschiebungen
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
Bezeichnet \(M_c\) die lineare Abbildung, die der komplexen Multiplikation mit \(c=(u,v)\) entspricht, so gilt
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
Mit \(A=M_a\) und \(B=M_b\) ist der gesamte unendliche Baum die eindeutige kompakte Menge mit
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
Für eine Richtung \(d\in\mathbb{R}^2\) definieren wir die Stützfunktion
$$h(d)=\sup_{x\in K} d\cdot x.$$
Zwei Standardidentitäten übersetzen die Mengenrekursion in eine skalare Rekursion:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
Damit erfüllt \(h\) exakt
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
Die Hilfsfunktion support_unit_square ist exakt, weil das Einheitsquadrat die Ecken \((0,0)\), \((1,0)\), \((0,1)\) und \((1,1)\) hat. Also
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
Die im Code verwendete transponierte Abbildung ist
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
Die Heap-Suche benötigt eine obere Schranke für jeden noch nicht vollständig aufgelösten Teilbaum. Der Solver nutzt \(R=5\), und diese Konstante folgt direkt aus derselben Selbstähnlichkeitsgleichung. Wenn für alle Punkte von \(K\) bereits \(\|x\|\le R\) gilt, dann liefert das Wurzelquadrat höchstens \(\sqrt{2}\), der linke Teilbaum höchstens \(1+\frac{4R}{5}\) und der rechte Teilbaum höchstens \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\). Es genügt also
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right).$$
Das reduziert sich auf \(R\ge 5\) und \(R\ge \frac{\sqrt{65}}{2}\); daher ist \(R=5\) sicher. Für eine affine Kopie \(u+M K\) erhält man dann die obere Schranke
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
Nach einem endlichen Kindwort \(w\) speichert das Programm genau das Paar \(\text{offset}=d\cdot u_w\) und \(\text{dir}=M_w^{\mathsf{T}}d\). Der exakte Beitrag ist \(\text{offset}+h(\text{dir})\), die untere Schranke ist \(\text{offset}+h_S(\text{dir})\), und die obere Schranke ist \(\text{offset}+\|\text{dir}\|R\). Die Prioritätswarteschlange expandiert immer zuerst den Knoten mit der größten oberen Schranke. Knoten mit Schranke \(\le \texttt{best}+\texttt{tol}\) werden verworfen. Da jede Kindabbildung die Norm um \(\frac{4}{5}\) bzw. \(\frac{3}{5}\) skaliert, fallen die relevanten Schranken geometrisch ab.
Sobald die Stützfunktion verfügbar ist, folgt die achsenparallele Box aus vier Richtungen:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
Die lokale Implementierung liefert
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
und damit
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
Bevor das unendliche Problem gelöst wird, überprüft die C++-Datei die erste Generation exakt. Das linke Kindquadrat hat die Ecken \((0,1)\), \((\frac{16}{25},\frac{37}{25})\), \((-\frac{12}{25},\frac{41}{25})\) und \((\frac{4}{25},\frac{53}{25})\). Das rechte Kindquadrat hat die Ecken \((\frac{16}{25},\frac{37}{25})\), \((1,1)\), \((\frac{28}{25},\frac{46}{25})\) und \((\frac{37}{25},\frac{34}{25})\). Zusammen mit dem Wurzelquadrat ergibt das die exakte Box
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
genau der Wert, den finite_depth_bbox(1) verifiziert.
SupportSolver speichert die Konstanten \(a\), \(b\), \(t_1\) und \(t_2\). Die Funktion apply_transpose_mul berechnet \(M_c^{\mathsf{T}}d\), support_unit_square wertet das Grundquadrat exakt aus, und der Heap enthält Tupel \((\text{upper\_bound},\text{offset},\text{dir})\). Die C++-Version benutzt long double, prüft die Geometrie der ersten Generation und testet zusätzlich die Fixpunktgleichung der Stützfunktion in den vier Kardinalrichtungen. Die Python- und Java-Versionen implementieren dieselbe Best-First-Suche mit denselben Konstanten, verzichten aber auf das zusätzliche Checkpoint-Gerüst.
Wenn eine Stützfunktionsanfrage \(N_d\) Knoten expandiert, kosten die Heap-Operationen \(O(N_d\log N_d)\) Zeit und \(O(N_d)\) Speicher. Für die Endfläche braucht man vier solche Anfragen, also bleibt die Gesamtordnung bis auf einen Faktor vier gleich. Das unterscheidet sich grundlegend von einer naiven Erzeugung bis Tiefe \(n\): Dort werden \(2^n\) Quadrate besucht, und selbst dann erhält man nur eine Approximation des unendlichen Baums. Hier ist die Suche adaptiv, weil ganze Teilbäume abgeschnitten werden, sobald ihre beste mögliche obere Schranke das aktuelle Optimum nicht mehr verbessern kann.
Problem 395, sonsuz Pythagoras ağacını tamamen içine alan eksenlere paralel sınırlayıcı dikdörtgenin alanını ister. Depodaki C++, Python ve Java çözümleri kareleri sabit bir derinliğe kadar üretmez. Bunun yerine ağacı öz-benzer bir küme \(K \subset \mathbb{R}^2\) olarak modeller, dört destek fonksiyonu uç değeri hesaplar ve sonunda \(28.2453753155\) sayısal alanını elde eder.
C++ doğrulama kodunda bir kare, başlangıç noktası \(p\) ve taban vektörü \(z\) ile temsil edilir. Dört köşesi
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
şeklindedir; burada \(i(x,y)=(-y,x)\) işlemi \(90^\circ\) döndürmedir. İki çocuk kare, taban vektörünün şu karmaşık-benzeri sabitlerle çarpılmasıyla oluşur:
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
Bunların uzunlukları \(|a|=\frac{4}{5}\) ve \(|b|=\frac{3}{5}\) olduğundan, her özyineleme adımı hem döndürür hem küçültür. Kök kare \(S=[0,1]^2\) için çözücünün kullandığı ötelemeler
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
\(c=(u,v)\) ile verilen karmaşık çarpmanın doğrusal karşılığına \(M_c\) dersek
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
\(A=M_a\) ve \(B=M_b\) olmak üzere tüm sonsuz ağaç şu afin sabit nokta denkleminden gelir:
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
Her \(d\in\mathbb{R}^2\) yönü için destek fonksiyonunu
$$h(d)=\sup_{x\in K} d\cdot x$$
şeklinde tanımlarız. İki temel özdeşlik kümeler üzerindeki özyinelemeyi skaler bir bağıntıya dönüştürür:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
Böylece tam destek değeri
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right)$$
eşitliğini sağlar. support_unit_square yardımcı fonksiyonu tamdır; çünkü birim karenin köşeleri \((0,0)\), \((1,0)\), \((0,1)\) ve \((1,1)\) olduğundan
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
Kodda yer alan transpoze dönüşüm de
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y)$$
biçimindedir.
Öncelik kuyruğu ile yapılan arama, henüz tam açılmamış her alt ağaç için bir üst sınıra ihtiyaç duyar. Çözücü \(R=5\) değerini kullanır ve bu sabit aynı öz-benzer denklemden doğrudan çıkar. Eğer \(K\) kümesindeki her nokta için \(\|x\|\le R\) ise kök kare en fazla \(\sqrt{2}\), sol alt ağaç en fazla \(1+\frac{4R}{5}\), sağ alt ağaç ise en fazla \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\) kadar uzaklaşabilir. Dolayısıyla
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right)$$
yeterlidir. Bu da \(R\ge 5\) ve \(R\ge \frac{\sqrt{65}}{2}\) koşullarına indirgenir; yani \(R=5\) güvenlidir. Herhangi bir \(u+M K\) afin kopyası için
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R$$
üst sınırını elde ederiz. Sonlu bir çocuk kelimesi \(w\) sonrasında program tam olarak \(\text{offset}=d\cdot u_w\) ve \(\text{dir}=M_w^{\mathsf{T}}d\) çiftini saklar. Kesin katkı \(\text{offset}+h(\text{dir})\), alt sınır \(\text{offset}+h_S(\text{dir})\), üst sınır ise \(\text{offset}+\|\text{dir}\|R\) olur. Öncelik kuyruğu her zaman en büyük üst sınıra sahip düğümü önce açar. Üst sınırı best + tol değerini aşmayan düğümler atılır. Her çocuk dönüşümü yön normunu \(\frac{4}{5}\) veya \(\frac{3}{5}\) ile çarptığı için umut veren üst sınırlar geometrik olarak küçülür.
Destek fonksiyonu bilindiğinde eksenlere paralel kutu dört koordinat yönünden elde edilir:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
Yerel çözücü şu değerleri verir:
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
ve buradan
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086$$
elde edilir.
Sonsuz problem çözülmeden önce C++ dosyası ilk nesli tam olarak doğrular. Sol çocuk karenin köşeleri \((0,1)\), \((\frac{16}{25},\frac{37}{25})\), \((-\frac{12}{25},\frac{41}{25})\) ve \((\frac{4}{25},\frac{53}{25})\) olur. Sağ çocuk karenin köşeleri ise \((\frac{16}{25},\frac{37}{25})\), \((1,1)\), \((\frac{28}{25},\frac{46}{25})\) ve \((\frac{37}{25},\frac{34}{25})\) olur. Kök kare ile birlikte bu, tam olarak
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right]$$
kutusunu verir; finite_depth_bbox(1) fonksiyonu tam bunu denetler.
SupportSolver, \(a\), \(b\), \(t_1\) ve \(t_2\) sabitlerini tutar. apply_transpose_mul fonksiyonu \(M_c^{\mathsf{T}}d\) hesabını yapar, support_unit_square kök kareyi tam değerlendirir ve kuyrukta \((\text{upper\_bound},\text{offset},\text{dir})\) üçlüleri saklanır. C++ sürümü long double kullanır, ilk nesil geometrisini kontrol eder ve ayrıca dört eksen yönü için destek sabit nokta eşitliğini doğrular. Python ve Java sürümleri aynı sabitlerle aynı best-first aramayı kullanır, ancak ek kontrol altyapısını içermez.
Bir destek sorgusu \(N_d\) düğüm açıyorsa, öncelik kuyruğu işlemleri \(O(N_d\log N_d)\) zaman ve \(O(N_d)\) bellek kullanır. Nihai alan için dört sorgu gerektiğinden toplam maliyet aynı mertebede kalır; sadece sabit çarpan artar. Bu yaklaşım, derinlik \(n\) için \(2^n\) kareyi gezen saf üretim yönteminden temelden farklıdır. Burada arama uyarlamalıdır; bir alt ağacın teorik olarak verebileceği en iyi üst sınır mevcut optimumu geçemiyorsa tüm dal tek adımda budanır.
El Problema 395 pide el área de la caja alineada con los ejes que contiene por completo el árbol pitagórico infinito. Las soluciones locales en C++, Python y Java no enumeran cuadrados hasta una profundidad fija. En su lugar modelan el árbol como un conjunto autosimilar \(K \subset \mathbb{R}^2\), resuelven cuatro consultas extremales de función soporte y obtienen finalmente el área numérica \(28.2453753155\).
En el código de verificación de C++, un cuadrado se representa mediante un punto inicial \(p\) y un vector base \(z\). Sus cuatro vértices son
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
donde \(i(x,y)=(-y,x)\) es una rotación de \(90^\circ\). Los dos cuadrados hijos se obtienen multiplicando el vector base por las constantes de tipo complejo
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
Sus módulos son \(|a|=\frac{4}{5}\) y \(|b|=\frac{3}{5}\), así que cada paso recursivo rota y además reduce la escala. Para el cuadrado raíz \(S=[0,1]^2\), las traslaciones usadas por el solver son
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
Si \(M_c\) denota la aplicación lineal asociada a la multiplicación compleja por \(c=(u,v)\), entonces
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
Con \(A=M_a\) y \(B=M_b\), el árbol infinito completo es el único conjunto compacto que satisface
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
Para una dirección \(d\in\mathbb{R}^2\), definimos la función soporte
$$h(d)=\sup_{x\in K} d\cdot x.$$
Dos identidades estándar convierten la ecuación de conjuntos en una recurrencia escalar:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
Por tanto, el valor exacto satisface
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
La función auxiliar support_unit_square es exacta porque el cuadrado unidad tiene vértices \((0,0)\), \((1,0)\), \((0,1)\) y \((1,1)\), así que
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
La acción transpuesta implementada por apply_transpose_mul es
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
La búsqueda con cola de prioridad necesita una cota superior para cada subárbol todavía no resuelto. El solver usa \(R=5\), y esa constante se deduce directamente de la misma ecuación autosimilar. Si todo punto de \(K\) cumple \(\|x\|\le R\), entonces el cuadrado raíz aporta como mucho \(\sqrt{2}\), el subárbol izquierdo aporta como mucho \(1+\frac{4R}{5}\), y el derecho como mucho \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\). Basta por tanto con exigir
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right).$$
Esto se reduce a \(R\ge 5\) y \(R\ge \frac{\sqrt{65}}{2}\), de modo que \(R=5\) es válido. Para cualquier copia afín \(u+M K\) obtenemos
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
Tras una palabra finita de hijos \(w\), el programa guarda exactamente \(\text{offset}=d\cdot u_w\) y \(\text{dir}=M_w^{\mathsf{T}}d\). La contribución exacta es \(\text{offset}+h(\text{dir})\), la cota inferior es \(\text{offset}+h_S(\text{dir})\), y la cota superior es \(\text{offset}+\|\text{dir}\|R\). La cola de prioridad expande siempre primero el nodo con mayor cota superior. Todo nodo cuya cota ya no supere best + tol se descarta. Como cada hijo reduce la norma de la dirección por \(\frac{4}{5}\) o \(\frac{3}{5}\), las cotas prometedoras decrecen geométricamente.
Una vez conocida la función soporte, la caja alineada con los ejes se obtiene a partir de las cuatro direcciones coordenadas:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
La implementación local produce
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
y por tanto
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
Antes de resolver el problema infinito, el archivo en C++ verifica exactamente la primera generación. El hijo izquierdo tiene vértices \((0,1)\), \((\frac{16}{25},\frac{37}{25})\), \((-\frac{12}{25},\frac{41}{25})\) y \((\frac{4}{25},\frac{53}{25})\). El hijo derecho tiene vértices \((\frac{16}{25},\frac{37}{25})\), \((1,1)\), \((\frac{28}{25},\frac{46}{25})\) y \((\frac{37}{25},\frac{34}{25})\). Junto con el cuadrado raíz, eso da la caja exacta
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
que es precisamente lo que comprueba finite_depth_bbox(1).
SupportSolver guarda las constantes \(a\), \(b\), \(t_1\) y \(t_2\). La función apply_transpose_mul calcula \(M_c^{\mathsf{T}}d\), support_unit_square evalúa exactamente el cuadrado base y la cola almacena ternas \((\text{upper\_bound},\text{offset},\text{dir})\). La versión en C++ usa long double, valida la geometría de profundidad 1 y además verifica la identidad de punto fijo de la función soporte en las cuatro direcciones cardinales. Las versiones en Python y Java implementan la misma búsqueda best-first con las mismas constantes, pero sin el arnés extra de comprobación.
Si una consulta de función soporte expande \(N_d\) nodos, las operaciones sobre la cola de prioridad cuestan \(O(N_d\log N_d)\) tiempo y \(O(N_d)\) memoria. El área final requiere cuatro consultas de ese tipo, así que el coste total mantiene el mismo orden salvo por un factor constante. Esto contrasta con una generación ingenua hasta profundidad \(n\), que visita \(2^n\) cuadrados y aun así solo aproxima el árbol infinito. Aquí la búsqueda es adaptativa: se podan subárboles completos tan pronto como su mejor cota posible ya no puede mejorar el óptimo actual.
第 395 题要求的是：找到能够完全覆盖无限 Pythagorean Tree 的轴对齐包围盒面积。仓库里的 C++、Python 和 Java 解法都没有把树展开到某个固定深度，而是把整棵树看成一个自相似集合 \(K \subset \mathbb{R}^2\)，对四个坐标方向分别求支持函数极值，最后得到数值面积 \(28.2453753155\)。
在 C++ 的检查代码中，一个正方形由起点 \(p\) 和底边向量 \(z\) 表示。它的四个顶点是
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
其中 \(i(x,y)=(-y,x)\) 表示逆时针旋转 \(90^\circ\)。两个子正方形通过把底边向量乘上下面这两个“复数式”常量得到：
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
它们的模分别为 \(|a|=\frac{4}{5}\) 和 \(|b|=\frac{3}{5}\)，所以每一步递归都同时带来旋转和缩放。对于根正方形 \(S=[0,1]^2\)，求解器使用的平移量是
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
如果 \(M_c\) 表示与复数乘法 \(c=(u,v)\) 对应的线性变换，那么
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
令 \(A=M_a\)、\(B=M_b\)，则整棵无限树就是满足下面不动点方程的唯一紧集：
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
对任意方向 \(d\in\mathbb{R}^2\)，定义支持函数
$$h(d)=\sup_{x\in K} d\cdot x.$$
集合上的两个标准恒等式可以把几何递推变成标量递推：
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
因此 \(h\) 满足精确方程
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
support_unit_square 之所以是精确公式，是因为单位正方形的顶点只有 \((0,0)\)、\((1,0)\)、\((0,1)\)、\((1,1)\)，所以
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
代码中的 apply_transpose_mul 实现的是
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
优先队列搜索需要为每个尚未完全展开的子树给出一个上界。程序采用 \(R=5\) 作为全局半径界，这个常数也能直接从自相似方程推出。若 \(K\) 中所有点都满足 \(\|x\|\le R\)，那么根正方形的最大距离不超过 \(\sqrt{2}\)，左子树不超过 \(1+\frac{4R}{5}\)，右子树不超过 \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\)。因此只要满足
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right)$$
即可。这会化成 \(R\ge 5\) 与 \(R\ge \frac{\sqrt{65}}{2}\)，所以 \(R=5\) 完全安全。于是对任意仿射拷贝 \(u+M K\)，都有
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
沿着某个有限孩子序列 \(w\) 向下时，程序保存的正是 \(\text{offset}=d\cdot u_w\) 与 \(\text{dir}=M_w^{\mathsf{T}}d\)。精确值是 \(\text{offset}+h(\text{dir})\)，下界是 \(\text{offset}+h_S(\text{dir})\)，上界则是 \(\text{offset}+\|\text{dir}\|R\)。优先队列总是优先展开上界最大的节点；若某节点上界已经不超过 best + tol，它就会被直接丢弃。由于两个子映射会把方向向量的范数分别乘上 \(\frac{4}{5}\) 与 \(\frac{3}{5}\)，有希望改进答案的上界会按几何级数衰减。
一旦支持函数可以计算，轴对齐包围盒就由四个坐标方向给出：
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
本地求解器得到
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
因此
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
在真正求无限树之前，C++ 文件先精确验证第一层几何。左孩子的四个顶点是 \((0,1)\)、\((\frac{16}{25},\frac{37}{25})\)、\((-\frac{12}{25},\frac{41}{25})\)、\((\frac{4}{25},\frac{53}{25})\)。右孩子的四个顶点是 \((\frac{16}{25},\frac{37}{25})\)、\((1,1)\)、\((\frac{28}{25},\frac{46}{25})\)、\((\frac{37}{25},\frac{34}{25})\)。再加上根正方形，就得到精确边界框
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
这正是 finite_depth_bbox(1) 检查的内容。
SupportSolver 保存常量 \(a\)、\(b\)、\(t_1\)、\(t_2\)。apply_transpose_mul 负责计算 \(M_c^{\mathsf{T}}d\)，support_unit_square 精确求根正方形的支持值，堆中存放的则是 \((\text{upper\_bound},\text{offset},\text{dir})\) 三元组。C++ 版本使用 long double，既验证第一层边界框，也验证四个坐标方向上的支持函数不动点关系。Python 与 Java 版本保留了同样的常量和 best-first 搜索逻辑，只是去掉了额外的检查框架。
若某个方向的支持函数查询一共展开 \(N_d\) 个节点，那么堆操作的时间复杂度为 \(O(N_d\log N_d)\)，空间复杂度为 \(O(N_d)\)。最终面积需要四次这样的查询，因此总体复杂度只是多了一个常数因子。这和朴素的深度 \(n\) 展开完全不同：朴素方法会访问 \(2^n\) 个正方形，而且仍然只能逼近无限树。这里的搜索是自适应的，只要某个子树的理论最优上界已经不可能超过当前最优值，整棵子树都会被一次性剪掉。
В задаче 395 требуется найти площадь осесимметричного bounding box, который покрывает всё бесконечное дерево Пифагора. Локальные решения на C++, Python и Java не разворачивают дерево до фиксированной глубины. Вместо этого они рассматривают дерево как самоподобное множество \(K \subset \mathbb{R}^2\), вычисляют четыре экстремальных значения опорной функции и получают итоговую площадь \(28.2453753155\).
В C++-проверке квадрат задаётся начальной точкой \(p\) и базовым вектором \(z\). Его четыре вершины имеют вид
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
где \(i(x,y)=(-y,x)\) означает поворот на \(90^\circ\). Два дочерних квадрата получаются умножением базового вектора на комплексоподобные коэффициенты
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
Их модули равны \(|a|=\frac{4}{5}\) и \(|b|=\frac{3}{5}\), поэтому каждый рекурсивный шаг одновременно поворачивает и уменьшает фигуру. Для корневого квадрата \(S=[0,1]^2\) решатель использует сдвиги
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
Если \(M_c\) обозначает линейное отображение, соответствующее умножению на комплексное число \(c=(u,v)\), то
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
При \(A=M_a\) и \(B=M_b\) всё бесконечное дерево является единственным компактным множеством, удовлетворяющим уравнению
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
Для направления \(d\in\mathbb{R}^2\) определим опорную функцию
$$h(d)=\sup_{x\in K} d\cdot x.$$
Две стандартные формулы переводят рекурсию по множествам в скалярную рекурсию:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
Следовательно, точное значение удовлетворяет равенству
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
Функция support_unit_square точна, потому что у единичного квадрата вершины \((0,0)\), \((1,0)\), \((0,1)\) и \((1,1)\), а значит
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
Транспонированное действие, реализованное в apply_transpose_mul, имеет вид
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
Поиск с приоритетной очередью требует верхней оценки для любого ещё не раскрытого поддерева. В решателе используется глобальная оценка \(R=5\), и она выводится из той же самоподобной структуры. Если все точки множества \(K\) удовлетворяют \(\|x\|\le R\), то корневой квадрат даёт максимум \(\sqrt{2}\), левое поддерево максимум \(1+\frac{4R}{5}\), а правое максимум \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\). Поэтому достаточно потребовать
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right).$$
Это сводится к условиям \(R\ge 5\) и \(R\ge \frac{\sqrt{65}}{2}\), так что \(R=5\) безопасен. Для любой аффинной копии \(u+M K\) получаем верхнюю оценку
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
После конечного слова дочерних переходов \(w\) программа хранит именно пару \(\text{offset}=d\cdot u_w\) и \(\text{dir}=M_w^{\mathsf{T}}d\). Точный вклад равен \(\text{offset}+h(\text{dir})\), нижняя оценка равна \(\text{offset}+h_S(\text{dir})\), а верхняя равна \(\text{offset}+\|\text{dir}\|R\). Приоритетная очередь всегда извлекает узел с наибольшей верхней оценкой. Узлы, для которых верхняя оценка уже не превосходит best + tol, отбрасываются. Поскольку дочерние отображения уменьшают норму направления в \(\frac{4}{5}\) или \(\frac{3}{5}\) раза, перспективные оценки убывают геометрически.
Как только умеем вычислять опорную функцию, осевой bounding box получается из четырёх координатных направлений:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
Локальный решатель выдаёт значения
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
и, следовательно,
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
Прежде чем решать бесконечную задачу, файл на C++ точно проверяет первое поколение. Левый дочерний квадрат имеет вершины \((0,1)\), \((\frac{16}{25},\frac{37}{25})\), \((-\frac{12}{25},\frac{41}{25})\) и \((\frac{4}{25},\frac{53}{25})\). Правый дочерний квадрат имеет вершины \((\frac{16}{25},\frac{37}{25})\), \((1,1)\), \((\frac{28}{25},\frac{46}{25})\) и \((\frac{37}{25},\frac{34}{25})\). Вместе с корневым квадратом это даёт точный прямоугольник
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
что и проверяет функция finite_depth_bbox(1).
SupportSolver хранит константы \(a\), \(b\), \(t_1\) и \(t_2\). Функция apply_transpose_mul вычисляет \(M_c^{\mathsf{T}}d\), support_unit_square точно вычисляет вклад базового квадрата, а в куче лежат тройки \((\text{upper\_bound},\text{offset},\text{dir})\). Версия на C++ использует long double, проверяет геометрию первого поколения и дополнительно контролирует уравнение неподвижной точки опорной функции для четырёх осевых направлений. Версии на Python и Java реализуют тот же поиск best-first с теми же константами, но без дополнительного тестового каркаса.
Если один запрос опорной функции раскрывает \(N_d\) узлов, то операции с приоритетной очередью занимают \(O(N_d\log N_d)\) времени и \(O(N_d)\) памяти. Для финальной площади нужны четыре таких запроса, так что итоговый порядок остаётся тем же с точностью до постоянного множителя. Это принципиально отличается от наивного разворачивания дерева до глубины \(n\), где посещаются \(2^n\) квадратов и всё равно получается лишь приближение бесконечного дерева. Здесь поиск адаптивен: целые поддеревья отсекаются сразу, как только их наилучшая возможная верхняя оценка уже не способна улучшить текущий максимум.
تطلب المسألة 395 حساب مساحة صندوق الاحتواء المحاذي للمحاور الذي يحتوي شجرة فيثاغورس اللانهائية كاملة. الحلول المحلية في ++C وPython وJava لا تولد المربعات حتى عمق ثابت، بل تنظر إلى الشجرة على أنها مجموعة ذاتية التشابه \(K \subset \mathbb{R}^2\)، ثم تحسب أربع قيم قصوى لدالة الدعم، وفي النهاية تحصل على المساحة العددية \(28.2453753155\).
في كود التحقق بلغة ++C، يُمثَّل كل مربع بنقطة بداية \(p\) ومتجه قاعدة \(z\). زواياه الأربع هي
$$p,\qquad p+z,\qquad p+i z,\qquad p+z+i z,$$
حيث إن \(i(x,y)=(-y,x)\) تعني دورانًا بمقدار \(90^\circ\). ويُنتج المربعان الابنان من ضرب متجه القاعدة في الثابتين الشبيهين بالأعداد المركبة
$$a=\left(\frac{16}{25},\frac{12}{25}\right),\qquad b=\left(\frac{9}{25},-\frac{12}{25}\right).$$
قيمتا الطول هما \(|a|=\frac{4}{5}\) و\(|b|=\frac{3}{5}\)، لذلك كل خطوة عودية تدور وتقلص في الوقت نفسه. بالنسبة إلى مربع الجذر \(S=[0,1]^2\)، فإن الإزاحتين المستخدمتين في الحل هما
$$t_1=(0,1),\qquad t_2=t_1+a=\left(\frac{16}{25},\frac{37}{25}\right).$$
إذا رمزنا بـ \(M_c\) إلى التحويل الخطي الموافق للضرب المركب في \(c=(u,v)\)، فإن
$$M_c(x,y)=(ux-vy,\ vx+uy).$$
وبأخذ \(A=M_a\) و\(B=M_b\)، تصبح الشجرة اللانهائية كلها هي المجموعة المضغوطة الوحيدة التي تحقق
$$K=S\cup (t_1+A K)\cup (t_2+B K).$$
لكل اتجاه \(d\in\mathbb{R}^2\)، نعرّف دالة الدعم بـ
$$h(d)=\sup_{x\in K} d\cdot x.$$
وهناك هويتان قياسيتان تحولان معادلة المجموعات إلى علاقة عددية:
$$h_{X\cup Y}(d)=\max\bigl(h_X(d),h_Y(d)\bigr),$$
$$h_{t+M X}(d)=d\cdot t+h_X(M^{\mathsf{T}}d).$$
ومن ثم فإن القيمة الدقيقة تحقق
$$h(d)=\max\left(h_S(d),\ d\cdot t_1+h(A^{\mathsf{T}}d),\ d\cdot t_2+h(B^{\mathsf{T}}d)\right).$$
الدالة المساعدة support_unit_square دقيقة تمامًا لأن رؤوس مربع الوحدة هي \((0,0)\) و\((1,0)\) و\((0,1)\) و\((1,1)\)، ولذلك
$$h_S(d)=\max(0,d_x,d_y,d_x+d_y).$$
أما التحويل المنقول الذي تنفذه apply_transpose_mul فهو
$$M_c^{\mathsf{T}}(d_x,d_y)=(u d_x+v d_y,\ -v d_x+u d_y).$$
البحث باستخدام طابور أولوية يحتاج إلى حد أعلى لكل جزء من الشجرة لم يُحسم بعد. يستخدم الحل القيمة \(R=5\) كحد شعاعي عام، ويمكن تبريرها مباشرة من معادلة التشابه نفسها. إذا كان كل عنصر في \(K\) يحقق \(\|x\|\le R\)، فإن مربع الجذر يساهم بما لا يزيد على \(\sqrt{2}\)، والفرع الأيسر بما لا يزيد على \(1+\frac{4R}{5}\)، والفرع الأيمن بما لا يزيد على \(\frac{\sqrt{65}}{5}+\frac{3R}{5}\). إذن يكفي أن يتحقق
$$R\ge \max\left(\sqrt{2},\ 1+\frac{4R}{5},\ \frac{\sqrt{65}}{5}+\frac{3R}{5}\right).$$
وهذا يكافئ الشرطين \(R\ge 5\) و\(R\ge \frac{\sqrt{65}}{2}\)، ولذلك فإن \(R=5\) حد آمن. ولكل نسخة affine من الشكل \(u+M K\) نحصل على
$$\sup_{x\in u+M K} d\cdot x \le d\cdot u+\|M^{\mathsf{T}}d\|R.$$
بعد أي كلمة محدودة من الاختيارات \(w\)، يخزن البرنامج الزوج \(\text{offset}=d\cdot u_w\) و\(\text{dir}=M_w^{\mathsf{T}}d\). القيمة الدقيقة لذلك الفرع هي \(\text{offset}+h(\text{dir})\)، والحد الأدنى هو \(\text{offset}+h_S(\text{dir})\)، والحد الأعلى هو \(\text{offset}+\|\text{dir}\|R\). ويقوم طابور الأولوية دائمًا بتوسيع العقدة ذات الحد الأعلى الأكبر أولًا. أما العقد التي صار حدها الأعلى لا يتجاوز best + tol فتُهمل فورًا. وبما أن كل ابن يضرب معيار الاتجاه في \(\frac{4}{5}\) أو \(\frac{3}{5}\)، فإن الحدود العليا المفيدة تتناقص هندسيًا.
بعد توفر دالة الدعم، يُستخرج الصندوق المحاذي للمحاور من الاتجاهات الأربعة القياسية:
$$x_{\max}=h(1,0),\qquad x_{\min}=-h(-1,0),$$
$$y_{\max}=h(0,1),\qquad y_{\min}=-h(0,-1).$$
ويعطي الحل المحلي القيم
$$x_{\min}\approx -3.235295198730329,\qquad x_{\max}\approx 3.130653549285805,$$
$$y_{\min}\approx -0.116075304973770,\qquad y_{\max}\approx 4.320871399047746,$$
ومن ثم
$$A=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\approx 28.245375315480086.$$
قبل حل الحالة اللانهائية، يتحقق ملف ++C بدقة من الجيل الأول. للمربع الأيسر الرؤوس \((0,1)\) و\((\frac{16}{25},\frac{37}{25})\) و\((-\frac{12}{25},\frac{41}{25})\) و\((\frac{4}{25},\frac{53}{25})\). وللمربع الأيمن الرؤوس \((\frac{16}{25},\frac{37}{25})\) و\((1,1)\) و\((\frac{28}{25},\frac{46}{25})\) و\((\frac{37}{25},\frac{34}{25})\). ومع مربع الجذر نحصل على صندوق الاحتواء الدقيق
$$\left[-\frac{12}{25},\frac{37}{25}\right]\times\left[0,\frac{53}{25}\right],$$
وهو بالضبط ما تتحقق منه الدالة finite_depth_bbox(1).
تحتفظ الفئة SupportSolver بالثوابت \(a\) و\(b\) و\(t_1\) و\(t_2\). وتحسب الدالة apply_transpose_mul المقدار \(M_c^{\mathsf{T}}d\)، بينما تحسب support_unit_square قيمة مربع الأساس بدقة، وتُخزن في الكومة ثلاثيات من الشكل \((\text{upper\_bound},\text{offset},\text{dir})\). تستخدم نسخة ++C النوع long double، وتتحقق من هندسة العمق الأول، كما تتحقق أيضًا من معادلة نقطة التثبيت لدالة الدعم في الاتجاهات المحورية الأربعة. أما نسختا Python وJava فتطبقان البحث نفسه من نوع best-first وبالثوابت نفسها، لكن من دون إطار التحقق الإضافي.
إذا كانت استعلامات دالة الدعم في اتجاه ما توسع \(N_d\) عقدة، فإن عمليات الكومة تكلف \(O(N_d\log N_d)\) زمنًا و\(O(N_d)\) ذاكرة. والمساحة النهائية تحتاج أربع استعلامات من هذا النوع، لذا يبقى نفس الترتيب مع اختلاف ثابت فقط. وهذا يختلف جذريًا عن التوليد الساذج حتى عمق \(n\)، لأنه يزور \(2^n\) مربعًا ومع ذلك لا يعطي إلا تقريبًا للشجرة اللانهائية. هنا البحث تكيفي؛ فبمجرد أن يصبح أفضل حد أعلى ممكن لفرع كامل غير قادر على تحسين القيمة الحالية، يُقلم ذلك الفرع كله دفعة واحدة.