<p>Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their <em><a href="https://en.wikipedia.org/wiki/Minkowski_addition" rel="nofollow">Minkowski sum</a></em>, defined as the set $\{ a + b : a\in A, b\in B \}$.</p>

<p>Is there any known result for the following problem?</p>

<blockquote>
  <p>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$? </p>
</blockquote>

<p>I am in particular interested in the case $d=2$. </p>

<p>A related result is the following: Given a <em>convex</em> 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.</p>

<p>[1] Gao, S., &amp; Lauder, A. G. (2001). <a href="http://arxiv.org/pdf/math/0012099" rel="nofollow">Decomposition of polytopes and polynomials</a>. <em>Discrete &amp; Computational Geometry</em>, 26(1), 89-104.</p>

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

CC BY-SA 3.0
2015-09-04T10:58:40.177Z
What about $A=S$ and $B$ contain only the zero vector?
Chao Xu
CC BY-SA 3.0
2015-09-04T12:03:43.727Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-09-04T12:45:19.510Z
@ChaoXu: Right, I forgot to mention that $|A|,|B|>1$.
Bruno
CC BY-SA 3.0
2015-09-04T12:49:41.740Z
@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$.
Bruno
CC BY-SA 3.0
2015-09-04T13:24:37.807Z
What is a point cloud?
Emil Jeřábek
CC BY-SA 3.0
2015-09-04T15:35:07.063Z
@EmilJeřábek: Simply a [set of points](https://en.wikipedia.org/wiki/Point_cloud). Maybe the term is not quite usual...
Bruno
<reference-request><cg.comp-geom>
Minkowski decomposition of lattice point cloud
Bruno
# Minkowski decomposition of lattice point cloud

(Asked by: username_0 on 2015-09-04)

Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their *[Minkowski sum](https://en.wikipedia.org/wiki/Minkowski_addition)*, 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](http://arxiv.org/pdf/math/0012099). *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$.

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_1**: What about $A=S$ and $B$ contain only the zero vector?  
> **username_2**: 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.  
> **username_0**: @ChaoXu: Right, I forgot to mention that $|A|,|B|>1$.  
> **username_0**: @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$.  
> **username_3**: What is a point cloud?  
> **username_0**: @EmilJeřábek: Simply a [set of points](https://en.wikipedia.org/wiki/Point_cloud). Maybe the term is not quite usual...  

---

## 0 answers

