A parallel approximation algorithm for minimum area polygonization based on clustering

Abstract

Minimum area polygonization is a well known NP-complete problem in computational geometry. It is the problem of finding a simple polygon with minimum area for a given set of points in the plane. We present a parallel approximation algorithm based on clustering to solve this problem in polynomial time. The algorithm has four phases: clustering the points into the meaningful parts, reclustering the big clusters to the smaller ones, finding minimum area polygon for each cluster and, finally merging the polygons. We implement the algorithm and present the results of experiments by comparing the previous works.