4
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What about $A=S$ and $B$ contain only the zero vector? $\endgroup$ – Chao Xu Sep 4 '15 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$ – Sasho Nikolov Sep 4 '15 at 12:03
  • $\begingroup$ @ChaoXu: Right, I forgot to mention that $|A|,|B|>1$. $\endgroup$ – Bruno Sep 4 '15 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 '15 at 12:49
  • $\begingroup$ What is a point cloud? $\endgroup$ – Emil Jeřábek Sep 4 '15 at 13:24

Your Answer

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

Browse other questions tagged or ask your own question.