6
$\begingroup$

Consider an arrangement of finitely-many open polygons in the plane (not necessarily convex) such that each polygon intersects at least two other non-intersecting polygons.

Is there always a sub-arrangement such that the union of all polygons in the sub-arrangement contains a hole?

In the illustration below, the blue arrangement on the left satisfies the requirements and indeed it contains a hole; the brown arrangement on the right does not satisfy the requirements (each polygon intersects two other polygons, but these other polygons intersect), and it does not contain a hole.

enter image description here

$\endgroup$
8
  • 3
    $\begingroup$ Are polygons closed (=include their boundary)? $\endgroup$ Commented Jul 13, 2020 at 18:27
  • 3
    $\begingroup$ Am I allowed to use infinitely many polygons? $\endgroup$ Commented Jul 13, 2020 at 18:39
  • $\begingroup$ I think this questions needs additional details, as has been pointed out. Are these open or closed polygons? Does a hole mean an open set, or just any point inside a region surrounded by polygons? An informed answer will require a precise question. $\endgroup$
    – RSpeciel
    Commented Jul 13, 2020 at 20:13
  • $\begingroup$ Take the left picture. Simply add a fifth polygon that covers the hole. That fifth polygon intersects with two non-intersecting polygons. The others did so without the addition. $\endgroup$ Commented Jul 13, 2020 at 20:20
  • $\begingroup$ You probably get that hole, if you assume that every polygon is closed, and interesects with exactly two other polygons that don't intersect in turn. No guarantees yet :-) $\endgroup$ Commented Jul 13, 2020 at 20:23

3 Answers 3

2
$\begingroup$

Consider vertical and horizontal stripes, like in $8\times 8$ checkerboard. Each stripe intersects four pair-wise disjoint stripes, but the board has no holes.

Note

The answer above was given to the question in its first revision.

Subsequent edits added explicit requirement for the sets in question to be closed first, and then to be open, which rendered the answer irrelevant.

This looks like a chase, so fixing an answer doesn't make sense.
I restored it to its initial shape and do not care about it any more.

$\endgroup$
4
  • $\begingroup$ Do vertical stripes touch each other? If so, they intersect (if they are all closed they intersect in their boundary, if they are all open they intersect in their interior). $\endgroup$ Commented Jul 13, 2020 at 22:30
  • $\begingroup$ @ErelSegal-Halevi Yes, they do – if they are closed, as I intended. But I apparently have missed the sets must be open. This makes my example irrelevant. Thank you for pointing at the problem! :) $\endgroup$
    – CiaPan
    Commented Jul 14, 2020 at 7:33
  • $\begingroup$ @ErelSegal-Halevi It turned out it wasn't me who missed the openness requirement. I restored my answer and added a comment on it. Thank you. $\endgroup$
    – CiaPan
    Commented Jul 14, 2020 at 8:36
  • $\begingroup$ When I wrote the question I did not think that it matters whether the sets are open or closed. Sorry for the confusion. $\endgroup$ Commented Jul 14, 2020 at 20:55
2
$\begingroup$

I believe the following approach should work for all polygons (I assumed that (1) the polygons are open, (2) existence of holes refers to a non-trivial first homology group and (3) the condition means that all polygons intersecting a fixed polygon are mutually disjoint):

Let $\mathcal{P}=\{P_1,\ldots,P_n\}$ be the polygons. We first show that the union of some subsets of $\mathcal{P}$ has a hole.

By the assumption, re-ordering if necessary, we can assume that for some $(4\le) k\le n$ and for all $1\le i<j\le k$, $P_i\cap P_j\neq\emptyset $ iff $j=i+1$ or $(i,j)=(1,k)$. Using the Mayer-Vietoris sequence (for reduced homology) and the fact that polygons are contractible, we have:

If $P_i\cap P_{i+1}$ is not connected for some $i\in\{1,\ldots,k-2\}$, take the minimum such $i$, then $H_1(P_1\cup \cdots \cup P_{i+1})\simeq\tilde{H}_0(P_i\cap P_{i+1})$ is non-trivial. Otherwise, $H_1(P_1\cup \cdots \cup P_k)\simeq \tilde{H}_0((P_1\cup P_{k-1})\cap P_k)$, which is non-trivial by construction.

Suppose $H_1(\bigcup \mathcal{P})=0$, let $m$ be the smallest integer such that $H_1(P_1\cup\cdots\cup P_m)=0$. Since $(P_1\cup\cdots\cup P_{m-1})\cap P_m$ is a disjoint union of open polygons, it has a trivial first homology. Once again by Mayer-Vietoris, $0=H_1(P_1\cup\cdots\cup P_{m-1})\oplus H_1(P_m)\simeq H_1(P_1\cup\cdots\cup P_{m-1})$, a contradiction.

Edit: A later edit to the question has clarified that my assumption (3) is not what was intended. In any case, I will leave this answer as it is, because the question under assumption (3) is also a very interesting one.

$\endgroup$
1
$\begingroup$

I might have an approach for convex polygons. I am not sure if I understand your question correctly, so let me give an answer in the case of convex polygons for both of my interpretations:

  1. assuming that any set has to intersect two other sets which don‘t intersect each other, but it could also intersect pairs that do.

In that case, there does not need to be a hole, take e.g. your blue example and add a set that covers the hole. CiaPan‘s answer also gives another counterexample.

  1. assuming that each set intersects at least two other sets and any pair it intersects is non-intersecting.

In that case there has to be a hole: there is no triple of sets with a common intersection, so the nerve complex is 1-dimensional, i.e., a graph. It cannot be a tree (as otherwise some set would only intersect one other set), so it has some cycle. By the nerve theorem, the union of the sets thus has a hole.

I can imagine that a similar argument might work also for non-convex polygons, but I haven‘t thought i through.

$\endgroup$
2
  • $\begingroup$ I meant interpretation 1, but I should have asked: is there a subset of the polygons such that their union has a hole (so adding a large polygon that covers the hole does not invalidate the claim). What is a "nerve complex"? When I Google for it, I only find medications for nerve diseases... $\endgroup$ Commented Jul 13, 2020 at 22:36
  • 1
    $\begingroup$ Here is some info on the nerve theorem (I realized now that what I call „nerve complex“ is just called „nerve“, at least in this article) en.m.wikipedia.org/wiki/Nerve_of_a_covering $\endgroup$ Commented Jul 14, 2020 at 6:02

You must log in to answer this question.

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