$C$ is a convex planar figure and $C_1,\dots,C_n$ are pairwise-disjoint convex subsets of $C$, like this:

enter image description here

A convex-preserving partition of $C$ is a partition $C=E_1\cup\dots\cup E_N$, , such that $N\geq n$, the $E_i$ are pairwise-disjoint convex figures, and for every $i=1,\dots,n$: $C_i\subseteq E_i$, i.e, each existing figure is contained in a unique new figure, like this:

enter image description here

For every $C,C_1,\dots,C_n$, let $F(C,C_1,\dots,C_n)$ be the smallest cardinality $N$ of a convex-preserving partition.

For every $n$, let $G(n)$ be the largest value of $F(C,C_1,\dots,C_n)$, for all combinations of $C,C_1,\dots,C_n$.

What is $G(n)$?

  • Obviously $G(1)=1$.
  • By the half-plane separation theorem, $G(2)=2$.
  • By the above figure, $G(3)\geq 4$; there is apparently no convex-preserving partition with $N=3$.

What more can be said about $G(n)$?

Remark: I asked a similar question in cstheory.SE. There, $C$ and all its subsets were axis-parallel rectangles. In that case, I found an algorithm that proves $G(n)\leq 3n+1$.

  • 1
    $\begingroup$ I feel like the notion of Davenport-Schinzel sequence may be relevant to this problem - in particular, from the centroid of your body then the bodies that can be 'seen' in a circular arc form a D-S sequence of order 2 (no $xyxy$ sequences exist). You might be able to use this for some sort of onion-skin algorithm that achieves linear time complexity. $\endgroup$ Mar 2, 2016 at 20:34

1 Answer 1


I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

  • To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
  • To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs.

The "neighbor" relation defines a planar graph with $V=n$ vertexes. Euler's formula implies that in a planar graph (with at least 3 vertexes) the number of edges is bounded by: $E\leq 3V-6$. Hence, the number of holes is at most $2n-4$. Hence, $G(n)\leq 3n-4$.

The lower bound gives the tiling shown on the figure:

enter image description here

In the infinite tiling, each hexagon touches 6 holes and each holes touches 3 hexagons, so the number of holes is exactly $2n$. In the finite tiling, the number of holes is smaller since the holes near the boundary can be attached to their neighboring hexagons. So the number of holes is $2n-o(n)$ and $G(n)\geq 3n-o(n)$.

  • $\begingroup$ By "to each pair of neighborhood sets correspond at most two holes" you mean "to each unordered pair $\{i,j\}$, there are at most two different holes such that $C_i,C_j$ are neighbors of these holes"? $\endgroup$ Mar 1, 2016 at 13:10
  • $\begingroup$ What exactly is the lower bound? $G(n)=...$? $\endgroup$ Mar 1, 2016 at 14:04
  • $\begingroup$ About $2n+$const $\endgroup$ Mar 2, 2016 at 12:19
  • $\begingroup$ Or I am too optimistic and bounds are $2n+O(\sqrt{n})$. $\endgroup$ Mar 3, 2016 at 6:22
  • 1
    $\begingroup$ Each face is at least 3-gon. So, 2E>3F. Applying the Euler formula we get V-F/2>2 therefore V>F/2 (+2) $\endgroup$ Mar 10, 2016 at 9:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .