A parallel approximation algorithm for minimum area polygonization based on clustering

نویسندگانسعید آسعیدی,مهسا سهیل شمائی
نشریهUPB Scientific Bulletin, Series C: Electrical Engineering and Computer Science
شماره صفحات111
شماره مجلد84
نوع مقالهFull Paper
تاریخ انتشار2022-05-27
رتبه نشریهعلمی - پژوهشی
نوع نشریهالکترونیکی
کشور محل چاپایران
نمایه نشریهSCOPUS ,ISI-Listed

چکیده مقاله

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.

tags: Minimum area polygonization, Approximation algorithm, Hierarchical clustering, Partitional clustering, Computational geometry