主題
Search

階梯多邊形


StaircasePolygon

將最小外接矩形定義為包含給定格多邊形的最小矩形。如果格多邊形的周長等於其最小外接矩形的周長,則稱其為凸多邊形。(請注意,“凸”格多邊形不一定是在通常意義上的凸多邊形。)階梯多邊形則被定義為包含其外接矩形的兩個對角的凸多邊形 (Bousquet-Mélou 等人,1999)。

計算寬度為 m 的多邊形的面積生成函式 H_m(y,q),對於寬度為 4 的階梯多邊形,由下式給出

 H_4(q)=(q^4(1+2q+4q^2+6q^3+7q^4+6q^5+4q^6+2q^7+q^8))/((1-q)^2(1-q^2)^2(1-q^3)^2(1-q^4)),
(1)

其滿足

 H_4(1/q)=-H_4(q)
(2)

(Bousquet-Mélou 1992,Bousquet-Mélou 等人,1999)。各向異性面積和周長生成函式 G(x,y,q) 和偏生成函式 H_m(y,q),透過下式連線

 G(x,y,q)=sum_(m>=1)H_m(y,q)x^m,
(3)

滿足自反性和反演關係

 H_m(1/y,1/q)=-y^(m-1)H_m(y,q)
(4)

對於 m>=2

 G(x,y,q)+yG(x/y,1/y,1/q)=-x
(5)

(Bousquet-Mélou 等人,1999)。

具有階梯孔的階梯多邊形的各向異性面積和周長生成函式 G(x,y,q) 滿足 形式為 的反演關係

 G(x,y,q)+y^2G(x/y,1/y,1/q)
(6)

(Bousquet-Mélou 等人,1999)。

Knuth (2022) 考慮了將所有具有給定半周長的階梯多邊形打包到一個正方形中。


另請參閱

凸多連方, 自避多邊形, 階梯行走

使用 探索

參考文獻

Bousquet-Mélou, M. "凸多連方和線段堆。" 物理學雜誌 A:數學與通論 25, 1925-1934, 1992.Bousquet-Mélou, M.; Guttmann, A. J.; Orrick, W. P.; and Rechnitzer, A. "反演關係、互反性和多連方。" 2009年8月23日. http://arxiv.org/abs/math.CO/9908123.Knuth, D. E. Exercise 7.2.2.1-303 in 計算機程式設計藝術,第 4B 卷:組合演算法,第 2 部分。 紐約: Addison-Wesley, 2022.

在 中被引用

階梯多邊形

請引用為

Weisstein, Eric W. “階梯多邊形。” 來自 —— 資源。 https://mathworld.tw/StaircasePolygon.html

主題分類