0
$\begingroup$

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?

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

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.