点集的子集的最小外围凸包 [英] The minimum perimeter convex hull of a subset of a point set

问题描述

在平面上给出n个点。没有3是共线的。

Given n points on the plane. No 3 are collinear.

给出数字k。

找出k个点的子集，使得k点的凸包在k点子集的任何凸包中都具有最小的周长。

Find the subset of k points, such that the convex hull of the k points has minimum perimeter out of any convex hull of a subset of k points.

我可以想到一个天真的方法在O（n ^ k k log k）中运行。 （找到大小为k的每个子集的凸包，并输出最小值）。

I can think of a naive method runs in O(n^k k log k). (Find the convex hull of every subset of size k and output the minimum).

我认为这是一个NP问题，但是我找不到适合简化的任何东西

I think this is a NP problem, but I can't find anything suitable for reduction to.

有人对这个问题有想法吗？

Anyone have ideas on this problem?

例如，

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

结果：

{(0,0),(0,1),(1,0)}

由于该集合包含3个点的凸包，并且结果的周长小于其他任何3个点集的结果。

Since this set contains 3 points the convex hull of and the perimeter of the result is smaller than that of any other sets of 3 points.

推荐答案

这可以在O（kn ^ 3）时间和O（kn ^ 2）空间（或者如果需要实际点的情况下可以在O（kn ^ 3））中完成。

This can be done in O(kn^3) time and O(kn^2) space (or maybe O(kn^3) if you want the actual points).

本文： http ：//www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf

，具有用于最小地解决这个问题周长和其他权重函数（例如面积，内角总和等）遵循某些约束，即使标题中说的是最小面积（周长请参见推论5.3）。

by Eppstein et al, has algorithms to solve this problem for minimum perimeter and other weight functions like area, sum of internal angles etc which follow certain constraints, even though the title says minimum area (See Corollary 5.3 for perimeter).

这个想法是一种动态编程方法，如下所示（请阅读第4节的前几段）：

The basic idea is a dynamic programming approach as follows (read the first few paragraphs of Section 4):

假设S是给定的点集，Q是k的凸包

Suppose S is the given set of points and Q is the convex hull of k points with minimum perimeter.

让p1是Q的最底点，p2和p3是船体上按逆时针顺序的下一个点。

Let p1 be the bottom-most point of Q, p2 and p3 are the next points on the hull in counter-clockwise order.

我们可以将Q分解为一个三角形p1p2p3和一个k-1点Q'的凸包（与三角形p1p2p3共享边p1p3）。

We can decompose Q into a triangle p1p2p3 and a convex hull of k-1 points Q' (which shares the side p1p3 with triangle p1p2p3).

主要观察结果是Q'对于k-1是最优的，其中最底点是p1，下一个点是p3，并且Q'的所有点都位于线的同一侧p2-> p3。

The main observation is that Q' is the optimal for k-1, in which the bottommost point is p1 and the next point is p3 and all the points of Q' lie on the same side of the line p2->p3.

因此，为每个四元组（pi，pj，pk，m ），这样

Thus maintaining a 4d array of optimum polygons for the each quadruple (pi, pj, pk, m) such that

• 多边形是一个正好是S点m点的凸包。


• pi是多边形的最低点。


• pj是逆时针顺序的下一个顶点，


• 多边形的所有点都位于线pi-> pj的左侧。


• 所有点与pi一样位于pj-> pk的同一侧。

• the polygon is a convex hull of exactly m points of S.
• pi is the bottom most point of the polygon.
• pj is the next vertex in counter-clockwise order,
• all points of the polygon lie to the left of the line pi -> pj.
• all points lie on the same side of pj->pk as pi does.

可以帮助我们找到m = k的最佳多边形。

can help us find the optimum polygons for m=k, given the optimum polygons for m <= k-1.

论文准确地描述了如何做到这一点，以达到规定的时空范围。

The paper describes exactly how to go about doing that in order to achieve the stated space and time bounds.

希望有帮助。

这篇关于点集的子集的最小外围凸包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！