7
$\begingroup$

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

$\endgroup$
  • 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$ – Steven Stadnicki Mar 2 '16 at 20:34
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Erel Segal-Halevi Mar 1 '16 at 13:10
  • $\begingroup$ What exactly is the lower bound? $G(n)=...$? $\endgroup$ – Erel Segal-Halevi Mar 1 '16 at 14:04
  • $\begingroup$ About $2n+$const $\endgroup$ – Fedor Petrov Mar 2 '16 at 12:19
  • $\begingroup$ Or I am too optimistic and bounds are $2n+O(\sqrt{n})$. $\endgroup$ – Fedor Petrov Mar 3 '16 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$ – Arseniy Akopyan Mar 10 '16 at 9:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.