星狀多邊形

星狀多邊形（star-shaped polygon）是平面上屬於星形域的多邊形區域，即這個多邊形內部存在「可以看到整個多邊形邊界與整個多邊形內部所有區域^[1]」的點。^[2]

形式上，若多邊形 $P$ 中存在一點 $z$ 使得對於 $P$ 中的每一點 $p$ 與 $z$ 連成的線段 ${\overline {zp}}$ 完全位於 $P$ 內，則稱 $P$ 為星狀多邊形。^[3]所有的 $z$ （能夠看到整個多邊形邊界的點）形成的集合稱為星狀多邊形 $P$ 的核（下稱「星狀核」）。

如果星狀多邊形是凸多邊形，則任意兩個點間的連結距離（能夠保持在內部連接內部兩點的任意折線的最小線段數）為1。如果星狀多邊形不是凸多邊形，則這個星狀多邊形的核中的任兩點連結距離為1；如果星狀多邊形內兩點中有一點不在星狀核內，則這兩點的連結距離也为1，而如果星狀多邊形內两点都在星状核外，则这两点的连结距离可能為1或2；因此對於任意星狀多邊形，最大的連結距離為2^[4]^[5]。

例子

凸多邊形都屬於星狀多邊形，且其星狀核為自己本身。^{[註 1]}

星形正多邊形的簡單化多邊形^{[註 2]}都是星狀多邊形，其幾何中心總是位於星狀核內。

反平行四邊形和勒穆瓦訥六邊形（英语：Lemoine hexagon）也屬於星狀多邊形，其星狀核為一個點。^{[註 3]}

可見性多邊形（英语：Visibility_polygon）也屬於星狀多邊形，因為根據其定義，其每個點都必須從中心可見。^[7]

演算法

分辨一個多邊形是否為星狀多邊形並且找到星狀核中一點可以被制定為一個低維線性規劃問題，其可以在線性時間內完成星狀多邊形的判斷。^[8]^:16

多邊形的每條邊定義了一個有包含多邊形內部區域（對星狀多邊形而言可能是全部或局部）的半平面，該半平面的邊界位於包含該邊的直線上，且包含多邊形在該邊上任意鄰近點的點。星狀多邊形的星狀核是其所有內部區域半平面的交集。而使用分治法可以在 $Θ (N log N)$ 時間內找到任意一組 $N$ 個半平面的交集。^[3] 不過，如果僅只是要尋找星狀多邊形的星狀核的話，存在比上述更快的方法。例如，李德財和佛朗哥·P·普雷帕拉塔（英语：Franco P. Preparata）在1979年提出了一種可以在線性時間內找到星狀多邊形的星狀核之演算法。^[9]

參見

單調多邊形（英语：Monotone polygon）

註釋

^ ^1.0 ^1.1 ^1.2 證明：凸多边形具有以下性質：任兩頂點間的連線或對角線都位於其內部。因此可以得到凸多邊形任兩點間都可以只用一條直線連接到，同時也意味著，凸多邊形內任何一點連接到邊界的直線段皆存在，因此凸多邊形都屬於星狀多邊形，且其星狀核為自己本身。（因為凸多边形任意內部點都可以用一條直線段連接到其他任意內部點）
^ ^2.0 ^2.1 ^2.2 複雜多邊形可以簡單化，即將之化為簡單多邊形，具體作法就是給所有自相交處新增頂點，並移除位於多邊形最外周界內的邊和頂點，使之成為簡單多邊形。^[6]^:205–206
^ 證明：反平行四邊形和勒穆瓦訥六邊形（英语：Lemoine hexagon）都有一個特性：邊在中心附近的位置交叉並形成一點，且如果以這點來檢視多邊區域，將交叉的部分簡單化^{[註 2]}可以得到與該點相交的形狀為多個凸多邊形。已知凸多邊形都屬於星狀多邊形^{[註 1]}，且凸多邊形的星狀核為自己本身^{[註 1]}，因此該交叉點可以看到與其相交的其他所有簡單化^{[註 2]}之凸多邊形的內部及邊界，因此可以將該交叉點視為這些多邊形的星狀核，並視這些多邊形為星狀多邊形。

參考文獻

^ ^1.0 ^1.1 Bose, Prosenjit and Toussaint, Godfried. Geometric and computational aspects of manufacturing processes. Computers & graphics (Elsevier). 1994, 18 (4): 487–497 [2023-11-26]. （原始内容存档于2023-11-26）.
^ Ke, Yan, Polygon visibility algorithms for weak visibility and link distance problems, The Johns Hopkins University, 1990 [2023-11-26], （原始内容存档于2023-11-26）
^ ^3.0 ^3.1 Franco P. Preparata and Michael Ian Shamos. Computational Geometry – An Introduction. Springer-Verlag. 1985. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988.
^ Aichholzer, Oswin and Aurenhammer, Franz and Hurtado Díaz, Fernando Alfredo and Ramos, Pedro A and Urrutia, J. Two-convex polygons. 25th European Workshop on Computational Geometry (Université Libre de Bruxelles). 2009: 117–120 [2023-11-26]. （原始内容存档于2022-07-05）.
^ R. MajdNia. Extentions of algorithms for minimum bends geometric embedding of trees onto the points inside polygons (Master thesis论文). Computer engineering and IT dep., Amirkabir University of Tech. 2012-02.
^ Branko Grunbaum and Geoffrey C. Shephard. Regular Polygons (PDF). Mathematics Magazine. 1977, 50: 227–247,51 [2023-11-27]. （原始内容存档 (PDF)于2023-11-04）.
^ Arkin, E.; Mitchell, Joseph. An optimal visibility algorithm for a simple polygon with star-shaped holes (技术报告). Cornell University Operations Research and Industrial Engineering. 1987. 746.
^ J. Matoušek; M. Sharir; E. Welzl. A Subexponential Bound for Linear Programming (PDF). Algorithmica. 1996, 16: 498-516 [2023-11-16]. （原始内容存档 (PDF)于2023-04-23）.
^ Lee, D. T.; Preparata, F. P., An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM, July 1979, 26 (3): 415–421, S2CID 6156190, doi:10.1145/322139.322142, hdl:2142/74090 , （原始内容存档于September 24, 2017）
^ ^10.0 ^10.1 Gao, Mingcen and Cao, Thanh-Tung and Tan, Tiow-Seng and Huang, Zhiyong. Flip-flop: convex hull construction via star-shaped polyhedron in 3D. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 2013: 45–54 [2023-11-27]. （原始内容存档于2023-12-03）.

[convex_polygon_is_star-shaped-6] 1.0 ^1.1 ^1.2 證明：凸多边形具有以下性質：任兩頂點間的連線或對角線都位於其內部。因此可以得到凸多邊形任兩點間都可以只用一條直線連接到，同時也意味著，凸多邊形內任何一點連接到邊界的直線段皆存在，因此凸多邊形都屬於星狀多邊形，且其星狀核為自己本身。（因為凸多边形任意內部點都可以用一條直線段連接到其他任意內部點）

[simplize-8] 2.0 ^2.1 ^2.2 複雜多邊形可以簡單化，即將之化為簡單多邊形，具體作法就是給所有自相交處新增頂點，並移除位於多邊形最外周界內的邊和頂點，使之成為簡單多邊形。^[6]^:205–206

[9] 證明：反平行四邊形和勒穆瓦訥六邊形（英语：Lemoine hexagon）都有一個特性：邊在中心附近的位置交叉並形成一點，且如果以這點來檢視多邊區域，將交叉的部分簡單化^{[註 2]}可以得到與該點相交的形狀為多個凸多邊形。已知凸多邊形都屬於星狀多邊形^{[註 1]}，且凸多邊形的星狀核為自己本身^{[註 1]}，因此該交叉點可以看到與其相交的其他所有簡單化^{[註 2]}之凸多邊形的內部及邊界，因此可以將該交叉點視為這些多邊形的星狀核，並視這些多邊形為星狀多邊形。

[article_bose1994geometric-1] 1.0 ^1.1 Bose, Prosenjit and Toussaint, Godfried. Geometric and computational aspects of manufacturing processes. Computers & graphics (Elsevier). 1994, 18 (4): 487–497 [2023-11-26]. （原始内容存档于2023-11-26）.

[book_ke1990polygon-2] Ke, Yan, Polygon visibility algorithms for weak visibility and link distance problems, The Johns Hopkins University, 1990 [2023-11-26], （原始内容存档于2023-11-26）

[PS-3] 3.0 ^3.1 Franco P. Preparata and Michael Ian Shamos. Computational Geometry – An Introduction. Springer-Verlag. 1985. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988.

[inproceedings_aichholzer2009two-4] Aichholzer, Oswin and Aurenhammer, Franz and Hurtado Díaz, Fernando Alfredo and Ramos, Pedro A and Urrutia, J. Two-convex polygons. 25th European Workshop on Computational Geometry (Université Libre de Bruxelles). 2009: 117–120 [2023-11-26]. （原始内容存档于2022-07-05）.

[5] R. MajdNia. Extentions of algorithms for minimum bends geometric embedding of trees onto the points inside polygons (Master thesis论文). Computer engineering and IT dep., Amirkabir University of Tech. 2012-02.

[maa.org-7] Branko Grunbaum and Geoffrey C. Shephard. Regular Polygons (PDF). Mathematics Magazine. 1977, 50: 227–247,51 [2023-11-27]. （原始内容存档 (PDF)于2023-11-04）.

[am-10] Arkin, E.; Mitchell, Joseph. An optimal visibility algorithm for a simple polygon with star-shaped holes (技术报告). Cornell University Operations Research and Industrial Engineering. 1987. 746.

[11] J. Matoušek; M. Sharir; E. Welzl. A Subexponential Bound for Linear Programming (PDF). Algorithmica. 1996, 16: 498-516 [2023-11-16]. （原始内容存档 (PDF)于2023-04-23）.

[12] Lee, D. T.; Preparata, F. P., An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM, July 1979, 26 (3): 415–421, S2CID 6156190, doi:10.1145/322139.322142, hdl:2142/74090 , （原始内容存档于September 24, 2017）

[inproceedings_gao2013flip-13] 10.0 ^10.1 Gao, Mingcen and Cao, Thanh-Tung and Tan, Tiow-Seng and Huang, Zhiyong. Flip-flop: convex hull construction via star-shaped polyhedron in 3D. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 2013: 45–54 [2023-11-27]. （原始内容存档于2023-12-03）.

[1]

[2]

[3]

[4]

[5]

[註 1]

[註 2]

[註 3]

[7]

[8]

[9]

[10]

[6]

星狀多邊形

例子

演算法

相關概念

星狀多面體

參見

註釋

參考文獻

Portal di Ensiklopedia Dunia