starshapedness

Starshapedness, or star-shapedness, is a geometric property of a subset of Euclidean space. A set S is star-shaped if there exists a point x0 in S such that for every point x in S, the line segment from x0 to x lies entirely within S. The point x0 is called a center (or kernel point). If such a center exists, S is said to be star-shaped with respect to x0; the collection of all centers is called the kernel of S. A set is star-shaped if and only if its kernel is nonempty. Convex sets are always star-shaped, since any point in a convex set can serve as a center.

In the context of polygons, the kernel has a concrete construction. For a simple polygon, the kernel is the intersection of half-planes determined by the polygon’s edges (the interior side of each edge defines a half-plane). If this intersection is nonempty, the polygon is star-shaped, and any point inside the kernel sees every point of the polygon. The kernel can be empty, in which case the polygon is not star-shaped. Computing the kernel of a polygon can be done in linear time with respect to the number of vertices.

Examples and non-examples help illustrate the concept. A disk or any convex polygon is star-shaped, with the center being any interior point. Non-star-shaped shapes include a crescent or an annulus (ring): in these shapes, no single point can see every other point via a line contained entirely in the shape.

Applications of star-shapedness appear in computer graphics, where visibility and rendering rely on kernel concepts, and in computational geometry and robotics, where kernel computation informs visibility, sensing, and motion planning.