0
$\begingroup$

Is there a $\mathrm{poly}(N)$ algorithm for determining whether an arbitrary cellulation of a $2D$ plane has the following property:

  • There exists at least one non-empty subset $S$ of the cells such that every cell in $S$ borders an even number of cells not in $S$

I will also accept answers for dimensions $D>2$ if no result for $2D$ is forthcoming, and be very grateful for any results provided which are useful in tackling the problem.

$\endgroup$
3
  • $\begingroup$ You mean besides the subset $S=\emptyset$, every element of which borders on $0=2\times0$ cells not in $S$? Of course every such element also borders on 1 (and also on 2, and on 3, and, …) cells not in $S$. $\endgroup$
    – Paul Tanenbaum
    Commented May 18 at 18:30
  • $\begingroup$ Yes, besides $S = \emptyset$. I'll specify in the question. $\endgroup$
    – ComptonScattering
    Commented May 18 at 18:37
  • $\begingroup$ Make that a proper subset $S$ of the cells, because the full set also has that property trivially. $\endgroup$
    – Lieven
    Commented May 18 at 21:29

1 Answer 1

Reset to default
2
$\begingroup$

If there exists at least one cell with an even number of neighbours, then that cell as a singleton satisfies the requirement. Otherwise all cells have an odd number of neighbours, and then any pair of adjacent cells satisfies the requirement. That means all cellulations satisfy the property, and the time complexity is constant.

$\endgroup$

You must log in to answer this question.

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