# Convex hull that maximizes number of covered points

There is a set $$A$$ of 2D points, $$|A| = m$$. My task is to find a subset $$B \subset A$$, $$|B| = n$$, such that the convex hull based on $$B$$ minimizes the number of points from $$A$$, that do not lie in this convex hull.

Could you please refer to a literature or give me some hints, how to formulate this optimization problem?

• How big are $m$ and $n$? – RobPratt Apr 16 '20 at 20:33
• approx. m = 500 and n = 10 – matlap112 Apr 17 '20 at 9:57

Here's an integer linear programming formulation with $$O(m^3)$$ variables and constraints. Let $$\mathcal{T}=\{T \subseteq A: |T|=3\}$$ be the set of triangles with vertices in $$A$$. For each $$i \in A$$, let $$\mathcal{T}_i \subseteq \mathcal{T}$$ be the set of triangles whose convex hull contains $$i$$. For $$i\in A$$, let binary decision variable $$x_i$$ indicate whether $$i\in B$$, and let binary decision variable $$y_i$$ indicate whether point $$i$$ appears in the convex hull of $$B$$. For $$T\in\mathcal{T}$$, let binary decision variable $$z_T$$ indicate whether triangle $$T$$ is selected. The problem is to maximize $$\sum_{i\in A} y_i$$ subject to \begin{align} \sum_{i\in A} x_i &= n \tag 1\\ y_i &\le x_i + \sum_{T\in \mathcal{T}_i} z_T &&\text{for all i\in A} \tag 2\\ z_T &\le x_i &&\text{for all T\in\mathcal{T} and i\in T} \tag 3 \end{align} Constraint $$(1)$$ enforces $$|B|=n$$. Constraint $$(2)$$ forces a covered point to appear in $$B$$ or the convex hull of some triangle with vertices in $$B$$. Constraint $$(3)$$ enforces $$z_T=1 \implies i\in B$$ for all $$i\in T$$.

If $$O(m^3)$$ is too big, you can use dynamic column generation to construct useful members of $$\mathcal{T}$$ as needed. Alternatively, you can heuristically reduce the number of triangles by taking $$\mathcal{T}=\{T \subseteq \text{convexhull}(A): |T|=3\}$$.