代數決策樹模型（algebraic decision-tree model）

單純的決策樹模型只讓演算法問「x 是否小於 y？」。這對排序與搜尋夠用，但許多問題——尤其在幾何中——天生會問更豐富的問題，像「這個點是否在那條線上方？」或「這三個點是左轉還是右轉？」，這些涉及算術，而不只是比較兩個給定的數。代數決策樹模型拓寬了規則手冊：在每個節點，你可以計算輸入的一個多項式，並依其正負號分支。它是證明幾何與算術問題下界的合適競技場。

具體地，每個內部節點計算輸入座標的某個多項式 p，並測試 p > 0、p = 0 還是 p < 0，把計算送往三條分支之一；葉子宣布答案。單純的比較「x < y」是特例 p = y - x 加上正負號測試，所以這個模型包含比較模型，而且嚴格更強——它可以，例如，在一步內測試 x^2 + y^2 < r^2（某點是否在圓內？）。所收的成本是樹高，即最壞情況輸入上的正負號測試次數。此模型中的下界計算被逼出的正負號測試次數，而最深刻的技巧（Ben-Or 定理）把這個次數連結到幾何：若 YES 輸入的集合裂成 N 個互不相連的碎片，樹高就必須 Omega(log N)，因為矮樹無法觸及足夠多的分離區域。

為何要費心多這份一般性？因為它讓下界能對抗「真的做算術、而非只做比較」的演算法，這在計算幾何中至關重要，那裡座標會被相加、相乘與平方。誠實的提醒：即使這個更豐富的模型也非普世——它仍「不」涵蓋雜湊、間接定址或讀取一個數的位元表示，所以像元素相異性的 Omega(n log n) 下界在此成立，卻被 RAM 模型中的雜湊繞過。另外，界定「連通分量數目」在幾何上很微妙；這個技巧給出乾淨的 Omega(n log n) 型地板，但不是適用於每個問題的萬能方法。