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$.
Minkowski decomposition of lattice point cloud
reference request;cg.comp geom