Minimum Perimeter-Sum Partitions in the Plane

被引：0

作者：

Abrahamsen, Mikkel ^{[1
]}

de Berg, Mark ^{[2
]}

Buchin, Kevin ^{[2
]}

Mehr, Mehran ^{[2
]}

Mehrabi, Ali D. ^{[2
]}

机构：

[1] Univ Copenhagen, Dept Comp Sci, DK-2100 Copenhagen, Denmark

[2] TU Eindhoven, Dept Comp Sci, NL-5600 MB Eindhoven, Netherlands

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2020年 / 63卷 / 02期

关键词：

Computational geometry; Clustering; Minimum-perimeter partition; Convex hull; 2-CENTER; BIPARTITIONS; POINTS;

D O I：

10.1007/s00454-019-00059-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P-1 and P-2 such that the sum of the perimeters of ch(P-1) and CH(P-2) is minimized, where CH(P-i) denotes the convex hull of P-i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n(2)) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log(2) n) time and a (1 + epsilon)-approximation algorithm running in O(n + 1/epsilon(2) . log(2)(1/epsilon)) time.

引用

页码：483 / 505

页数：23