星状多边形

提示：此条目的主题不是星形多边形。

星状多边形（star-shaped polygon）是平面上属于星形域的多边形区域，即这个多边形内部存在“可以看到整个多边形边界与整个多边形内部所有区域^[1]”的点。^[2]

星状多边形（上方）。其星状核在下方以红色表示

形式上，若多边形P中存在一点z使得对于P中的每一点p与z连成的线段${\displaystyle {\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]

相关概念

星状多面体

星状多面体（star-shaped polyhedron）是星状多边形在三维空间的推广。 指一个多面体中至少包含一个点能从该点看到多面体所有区域和边界以及多面体内部的其他所有点。^[1][10]

能够看到整个星状多面体的区域同样称为该星状多面体的核，也就是其星状核。^[10]

参见

• 单调多边形（英语：Monotone polygon）