Star-shaped polygon

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.

Testing whether a polygon is star-shaped, and finding a single point in the kernel, may be solved in linear time by formulating the problem as a linear program and applying techniques for low-dimensional linear programming (see http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, page 16).

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.

[1] However, for the case of kernels of polygons, a faster method is possible: Lee & Preparata (1979)[2] presented an algorithm to construct the kernel in linear time.