Sparse convex hull coverage
Sparse convex hull coverage
复制标题
DOI：
10.1016/j.comgeo.2021.101787
复制
发表时间：
2021-05-21
影响因子：
0.6
通讯作者：
Van Buskirk, Gregory
中科院分区：
文献类型：
--
作者：
Klimenko, Georgiy;Raichel, Benjamin;Van Buskirk, Gregory
给定 n 个数据点的集合 P 和整数 k，基本计算任务是找到仅包含 k 个点的 P 的较小子集 Q 子集，该子集近似保留 P 的几何形状。这里我们考虑找到最能捕获 P 的凸包的 k 点的子集 Q 的问题，其中我们的误差度量是 P 中的点到 Q 的凸包的距离之和。我们概括该问题以允许我们必须从中选择 Q 的集合 R 与 P 不同，并允许更多P 的未覆盖点的距离的一般函数，例如其他范数或加权距离函数。我们证明，在平面上以这种方式逼近凸包可以通过基于简单图的算法或基于动态规划的算法在多项式时间内求解。补充这个结果，我们表明在三个维度及更高维度中，该问题是 NP 困难的。此外，我们给出了一种算法，该算法在三个维度上选择 O(k log(n/epsilon)) 点来获得误差至多为最佳 k 点误差 1 + epsilon 倍的解。对于任何常数维度 d，这可推广到 O(k([d/2]) log(n/epsilon)) 点。 (C) 2021 Elsevier B.V. 保留所有权利。
Given a set P of n data points and an integer k, a fundamental computational task is to find a smaller subset Q subset of P of only k points which approximately preserves the geometry of P. Here we consider the problem of finding the subset Q of k points which best captures the convex hull of P, where our error measure is the sum of the distances of the points in P to the convex hull of Q. We generalize the problem to allow the set R that we must select Q from to differ from P, as well as to allow more general functions of the distances of the uncovered points of P, such as other norms or weighted distance functions.We prove that approximating the convex hull in this manner in the plane can be solved by either a simple graph based or dynamic programming based algorithm in polynomial time. Complementing this result we show that in three dimensions and higher the problem is NP-hard. Moreover, we give an algorithm which in three dimensions selects O(k log(n/epsilon)) points to get a solution whose error is at most 1 + epsilon times the optimal k point error. This generalizes to O(k([d/2]) log(n/epsilon)) points for any constant dimension d. (C) 2021 Elsevier B.V. All rights reserved.