In a paper by Jack Edmonds and Laura Sanità (link: https://www.sciencedirect.com/science/article/pii/S1571065310001605) the following intriguing result is given: Given a triangulation $T$ of $3n$ points in the plane, if there is a partitioning $R$ of $T$, then there must also be a different partitioning $R'$ of $T$ (or more broadly, the number of partitionings is even).

A partitioning $R$ of $T$ (the room-partitioning in the title) is a set $R$ of $n$ triangular faces of $T$ such that each input point is in exactly one triangle of $R$.

The result is given as an example of a broader class of search problems; given $R$ we can find a different $R'$ through a sequence of local exchanges (this may take exponential time), so existence is guaranteed but no poly-time algorithm is known.

My question: what about deciding whether $T$ has even one such partitioning? Is this known to be NP-hard?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.