I just encountered the following problem:

$L:$ Given positive integers $n\geq 3,k\geq1$, decide whether it is possible to divide an $n$-polygon into $k$ equally shaped and equally sized pieces where each piece should be connected within itself.

For some $n$ it is trivial, e.g. $\forall k:(4,k)\in L$, $\forall k|2n:(n,k)\in L.$ But for some other, it seems hard to decide.

By promising each input be either out of $L$ or could be divided by finite number of straight lines (segments), and further assuming these lines all passes through some rational coefficient pair of points on the plane, then we'll be able to verifiy the solution in poly-time. But I personally do not find this assumption convincing, and do not have any further idea.

Is there any algorithmic stratedy to decide $L$, or else, it should be too hard to solve?


Most lines cannot be parametrized into rational parameters, by picking $\alpha_1,\alpha_2,\alpha_3,\alpha_4$, $\forall i\neq j:\mathbb{Q}(\alpha_i)\not\subseteq \mathbb{Q}(\alpha_j)$ and assign the line passing through $(\alpha_1,\alpha_2),(\alpha_3,\alpha_4)$, it will not pass through any rational point.


Your Answer

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

Browse other questions tagged or ask your own question.