星状多边形
星状多边形（star-shaped polygon）是平面上属于星形域的多边形区域，即这个多边形内部存在“可以看到整个多边形边界与整个多边形内部所有区域[1]”的点。[2]
形式上，若多边形P中存在一点z使得对于P中的每一点p与z连成的线段完全位于P内，则称P为星状多边形。[3]所有的z（能够看到整个多边形边界的点）形成的集合称为星状多边形P的核（下称“星状核”）。
如果星状多边形是凸多边形，则任意两个点间的连结距离（能够保持在内部连接内部两点的任意折线的最小线段数）为1。 如果星状多边形不是凸多边形，则这个星状多边形的核中的任两点连结距离为1；如果星状多边形内两点中有一点不在星状核内，则这两点的连结距离也为1，而如果星状多边形内两点都在星状核外，则这两点的连结距离可能为1或2；因此对于任意星状多边形，最大的连结距离为2[4][5]。
例子
凸多边形都属于星状多边形，且其星状核为自己本身。[注 1]
星形正多边形的简单化多边形[注 2]都是星状多边形，其几何中心总是位于星状核内。
演算法
分辨一个多边形是否为星状多边形并且找到星状核中一点可以被制定为一个低维线性规划问题，其可以在线性时间内完成星状多边形的判断。[8]:16
多边形的每条边定义了一个有包含多边形内部区域（对星状多边形而言可能是全部或局部）的半平面，该半平面的边界位于包含该边的直线上，且包含多边形在该边上任意邻近点的点。 星状多边形的星状核是其所有内部区域半平面的交集。而使用分治法可以在Θ(N log N)时间内找到任意一组N个半平面的交集。[3] 不过，如果仅只是要寻找星状多边形的星状核的话，存在比上述更快的方法。 例如，李德财和佛朗哥·P·普雷帕拉塔在1979年提出了一种可以在线性时间内找到星状多边形的星状核之演算法。[9]
相关概念
星状多面体
星状多面体（star-shaped polyhedron）是星状多边形在三维空间的推广。 指一个多面体中至少包含一个点能从该点看到多面体所有区域和边界以及多面体内部的其他所有点。[1][10]
能够看到整个星状多面体的区域同样称为该星状多面体的核，也就是其星状核。[10]
参见
注释
- ^ 1.0 1.1 1.2 证明：凸多边形具有以下性质：任两顶点间的连线或对角线都位于其内部。因此可以得到凸多边形任两点间都可以只用一条直线连接到，同时也意味著，凸多边形内任何一点连接到边界的直线段皆存在，因此凸多边形都属于星状多边形，且其星状核为自己本身。（因为凸多边形任意内部点都可以用一条直线段连接到其他任意内部点）
- ^ 2.0 2.1 2.2 复杂多边形可以简单化，即将之化为简单多边形，具体作法就是给所有自相交处新增顶点，并移除位于多边形最外周界内的边和顶点，使之成为简单多边形。[6]:205–206
- ^ 证明：反平行四边形和勒穆瓦讷六边形都有一个特性：边在中心附近的位置交叉并形成一点，且如果以这点来检视多边区域，将交叉的部分简单化[注 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）.
