In
geometry
Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
, a star-shaped polygon is a
polygonal region in the plane that is a
star domain, that is, a polygon that contains a point from which the entire polygon boundary is
visible.
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 polytop ...
, the
link distance 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 ...
s are star shaped, and a convex polygon coincides with its own kernel.
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 theoretical 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 ...
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 and objective are represented by linear relationships. Linear ...
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
In mathematics, the upper half-plane, is the set of points in the Cartesian plane with The lower half-plane is the set of points with instead. Arbitrary oriented half-planes can be obtained via a planar rotation. Half-planes are an example ...
, 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 (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
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.
[ However, for the case of kernels of polygons, a faster method is possible: ]
See also
* Monotone polygon
References
{{polygons
Types of polygons
Geometric algorithms