Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$.

Is there any known result for the following problem?

Given a point cloud $S\subset\mathbb Z^d$, are there two point clouds $A$ and $B$, none of them reduced to a single point, such that $A\oplus B = S$?

I am in particular interested in the case $d=2$.

A related result is the following: Given a convex set of points¹ $S\subset\mathbb Z^2$, it is $\mathsf{NP}$-hard to decide whether it can be written as the sum of two convex sets $A$ and $B$ [1]. As far as I can tell, this does not imply a hardness result for the above problem since the equality is on the convex hulls only, not on the point clouds. In the terminology I used above, in this problem is only required that $A\oplus B\subset S$. The problem on point clouds may well be easier (not $\mathsf{NP}$-hard in particular) since it is much more constrained.

[1] Gao, S., & Lauder, A. G. (2001). Decomposition of polytopes and polynomials. Discrete & Computational Geometry, 26(1), 89-104.

¹ A subset $S\subset\mathbb Z^d$ is said convex if all points of $S$ lie on the boundary of the convex hull of $S$.

  • 1
    $\begingroup$ What about $A=S$ and $B$ contain only the zero vector? $\endgroup$
    – Chao Xu
    Sep 4, 2015 at 10:58
  • $\begingroup$ It doesnt really make sense to say that a subset of $\mathbb{Z}^2$ is convex. The problem in [1] is to decide, given a finite $S \subset \mathbb{Z}^2$, whether there exist finite sets $A, B \subset \mathbb{Z}^2$, $|A|, |B| > 1$, such that $\mathrm{conv}\ S = \mathrm{conv}\ A + \mathrm{conv}\ B$, where $\mathrm{conv}$ is the convex hull operator. $\endgroup$ Sep 4, 2015 at 12:03
  • $\begingroup$ @ChaoXu: Right, I forgot to mention that $|A|,|B|>1$. $\endgroup$
    – Bruno
    Sep 4, 2015 at 12:45
  • $\begingroup$ @SashoNikolov: You're completely right on the formulation of the problem in [1]. I wanted to express it in closest possible language as "my" problem. I add a definition of "convex" for a subset of $\mathbb Z^2$. $\endgroup$
    – Bruno
    Sep 4, 2015 at 12:49
  • $\begingroup$ What is a point cloud? $\endgroup$ Sep 4, 2015 at 13:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.