Minimum polygonal separation (Q1101685)

A convex k-gon is the intersection of k but no fewer halfplanes. A convex k-gon is a k-separator of two point sets if it contains one and its interior avoids the other. The problem of polygonal separation is as follows: for given two finite sets of points in the plane, construct a k- separator for the smallest possible k. By tracing back a sorting to a polygonal separation, the authors show that the computational complexity of polygonal separation is \(\Omega\) (n log n), if n points are involved. Two algorithms are presented. The first computes the convex hull of the internal set and a nested star-shaped polygon determined by the external set in O (n log n) time and then finds the k-separator between them in linear time. If the actual k is o(log n), the second algorithm is better. This is a prune-and-search algorithm, which yields one edge of the separator in each iteration. Its running time is O(kn), but may give one more side than the minimum.