An efficient algorithm for decomposing a polygon into star-shaped polygons

摘要

In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.