1
$\begingroup$

Let $P$ be a convex polygon with $n\ge3$ vertices. Let $\mathcal{Z}_K(P)$ be a partition of the polygon into $K$ polygonal (but not necessarily convex) parts whose interiors are pairwise disjoint, $$ \mathcal{Z}_K(P)=\{p_1,\ldots,p_K\}\quad\text{s.t.}\quad \operatorname{int}(p_i) \cap \operatorname{int}(p_j)=\emptyset\;\forall i\neq j\quad\wedge\quad \bigcup_{i=1}^K p_i=P. $$

Question. Is it true for every $K$, that there is such a partition $\mathcal{Z}_K(P)$ that allows all parts $p_i$ to share at least one edge or vertex with every other part $p_{j\neq i}$?

I tried for $n=4$ and $K=2,3,4$ and succeeded (trivial), but I got stuck at $K=5$. I tried to search for this specific partitioning but I couldn't find anything relevant.

I only found out that if we let $k_i$ be the centroid of the i-th part $p_i$, and connect such centroid to all other centroids $k_{j\neq i}$ of polygonal parts that share at least one edge or vertex with every other part, the resulting graph will have an all-ones adjacency matrix.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ Could you clarify your notation slightly? I believe you want to specify that the $p_i$ are pairwise disjoint, instead of saying the intersection of all of them is empty. Also I get confused by what is a "part", what is "partition" and what is "partitioning". Are $p_i$ polygonal parts (subsets) of $P$? Is ${\cal Z}_K(P)$ a partition into $K$ such polygonal parts, as your notation says, or is it the set of all such partitions? $\endgroup$
    – Jukka Kohonen
    Commented Apr 30, 2021 at 0:21
  • 4
    $\begingroup$ Why is this not a solution? Let $x$ be any strictly interior point of $P$. Draw spokes from $x$ to the boundary of $P$, with adjacent spokes separated by $2 \pi /K$. The resulting pieces $p_i$ each share $x$. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 30, 2021 at 0:37
  • 1
    $\begingroup$ Fedor, my guess is the OP means that their interiors must have empty intersection. This is another thing that should be clarified in the question. $\endgroup$
    – Jukka Kohonen
    Commented Apr 30, 2021 at 6:18
  • 1
    $\begingroup$ Thanks, it is clearer now. Is it also so that the INTERIORS of the parts must be pairwise disjoint? (Otherwise surely they cannot share a vertex or an edge.) Still it seems Joseph's comment would provide an easy solution, so is this what you are after, or something else? $\endgroup$
    – Jukka Kohonen
    Commented Apr 30, 2021 at 10:38
  • 5
    $\begingroup$ In this case, for $K=5$ you will get an embedding of $K_5$ in the plane. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 30, 2021 at 12:16

1 Answer 1

Reset to default
3
$\begingroup$

Just to follow up @IlyaBogdanov's observation: a $k=4$ partition, whose pieces pairwise share an edge, can be achieved (below), corresponding to a planar embedding of $K_4$. But realizing the same for $k=5$ would would lead to planar embedding of $K_5$, which is impossible.

     K4

Improve this answer
$\endgroup$

You must log in to answer this question.

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