生成不包含指定点子集的最大面积2D凸包：算法与复杂度问询

Let's break your problem down into two clear parts: existing algorithms to solve it, and its computational complexity (whether it's NP-hard).

1. Are there existing algorithms for this problem? #

First, let's formalize your problem to avoid ambiguity:

Given a 2D point set S and a specified subset X ⊆ S (points we want to exclude from the convex hull's interior/boundary), find a subset T ⊆ S \ X such that the convex hull of T (denoted conv(T)) contains no points from X, and the area of conv(T) is maximized.

Yes, there are approaches tailored to this problem, though their efficiency depends on the size of your point sets:

• Trivial case first: Compute the convex hull of S \ X directly. If this convex hull does not contain any points from X, this is your optimal solution—since adding more points from S \ X can only keep the area the same or increase it, and we already included all of them.

• If the full convex hull of S \ X includes points from X:

  • Branch-and-bound exact algorithms: For smaller point sets (say, ≤20 points in S \ X), you can enumerate candidate convex polygons (vertices from S \ X), check if they exclude all points in X, and track the maximum area. Branch-and-bound prunes branches where the potential maximum area can't exceed the current best, making this feasible for small inputs.
  • Heuristic/approximation methods: For larger datasets, you can use heuristic approaches:
    • Start with the full convex hull of S \ X, then iteratively remove vertices that "allow" X points inside the hull, recomputing the convex hull each time until no X points are contained. Then, try reintroducing inner points from S \ X to expand the hull area where possible.
    • Sample subsets of S \ X (focusing on outer-layer points), compute their convex hulls, filter those that exclude X, and keep the largest one. This won't guarantee optimality, but it's fast.

This problem is a variant of the maximum empty convex hull problem, and you'll find related research in computational geometry literature focusing on constrained convex hull optimization.

2. Is this problem NP-hard? #

Yes, this problem is NP-hard. Here's why:
It can be reduced to the well-known Maximum Empty Convex Polygon (MECP) problem, which is proven NP-hard. MECP asks: given a point set S, find the largest-area convex polygon with vertices from S that contains no other points from S in its interior.

To see the reduction:
Take an MECP instance (point set S). Construct our problem's instance by setting X to be all points in S except the vertices of the convex polygon we're seeking. Our problem then becomes exactly MECP—we need a convex hull (polygon) that excludes all X points (the non-vertex points from S). Since MECP is NP-hard, our problem is at least as hard, hence NP-hard.

Even if we relax the problem to allow S \ X points inside the convex hull (as long as no X points are present), the core difficulty remains—finding the largest convex region that excludes a set of forbidden points is inherently hard to solve optimally in polynomial time.

内容的提问来源于stack exchange，提问作者gayan_lanke