In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, a star-shaped polygon is a
polygonal region in the plane that is a
star domain
In geometry, a set S in the Euclidean space \R^n is called a star domain (or star-convex set, star-shaped set or radially convex set) if there exists an s_0 \in S such that for all s \in S, the line segment from s_0 to s lies in S. This defini ...
, that is, a polygon that contains a point from which the entire polygon boundary is
visible
Visibility, in meteorology, is a measure of the distance at which an object or light can be seen.
Visibility may also refer to:
* A measure of turbidity in water quality control
* Interferometric visibility, which quantifies interference contrast ...
.
Formally, a polygon is star-shaped if there exists a point such that for each point of the segment lies entirely within .
The
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of all points with this property (that is, the set of points from which all of is visible) is called the kernel of .
If a star-shaped polygon is
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
, the
link distance In computational geometry, the link distance between two points in a polygon is the minimum number of line segments of any polygonal chain within the polygon that has the two points as its endpoints. The link diameter of the polygon is the maximum ...
between any two of its points (the minimum number of sequential line segments sufficient to connect those points) is 1, and so the polygon's link diameter (the maximum link distance over all pairs of points) is 1. If a star-shaped polygon is not convex, the link distance between a point in the kernel and any other point in the polygon is 1, while the link distance between any two points that are in the polygon but outside the kernel is either 1 or 2; in this case the maximum link distance is 2.
Examples
Convex polygon
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
s are star shaped, and a convex polygon coincides with its own kernel.
Regular
star polygon
In geometry, a star polygon is a type of non-convex polygon. Regular star polygons have been studied in depth; while star polygons in general appear not to have been formally defined, certain notable ones can arise through truncation operations ...
s are star-shaped, with their center always in the kernel.
Antiparallelogram
In geometry, an antiparallelogram is a type of self-crossing quadrilateral. Like a parallelogram, an antiparallelogram has two opposite pairs of equal-length sides, but these pairs of sides are not in general parallel. Instead, sides in the lon ...
s and self-intersecting
Lemoine hexagon
In geometry, the Lemoine hexagon is a cyclic hexagon with vertices given by the six intersections of the edges of a triangle and the three lines that are parallel to the edges that pass through its symmedian point. There are two definitions of th ...
s are star-shaped, with the kernel consisting of a single point.
Visibility polygons are star-shaped as every point within them must be visible to the center by definition.
Algorithms
Testing whether a polygon is star-shaped, and finding a single point in the kernel, may be solved in
linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by formulating the problem as a
linear program
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
and applying techniques for low-dimensional linear programming (see http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, page 16).
Each edge of a polygon defines an interior
half-plane, the half-plane whose boundary lies on the line containing the edge and that contains the points of the polygon in a
neighborhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...
of any interior point of the edge. The kernel of a polygon is the intersection of all its interior half-planes. The intersection of an arbitrary set of ''N'' half-planes may be found in
Θ(''N'' log ''N'') time using the
divide and conquer approach
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
.
[ However, for the case of kernels of polygons, a faster method is possible: ]
See also
*Monotone polygon
In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects the boundary of ''P'' at most twice.
Similarly, a polygonal chain ''C'' is called monotone with respec ...
References
{{polygons
Types of polygons
Geometric algorithms