4
$\begingroup$

Let $P$ be a given polygon in $\mathbb{R}^{2}$ such that all the vertices lie on integral points $\mathbb{Z}^{2}$. An integral polygonal sub-divison of $P$ is a subdivison of $P$ into integral sub-polygons. I would like to know:

If there is an algorithm to generate all such sub-divisons? I would prefer an easier to implement (possibly less efficient) algorithm over a more efficient one. I do not want probabilistic algorithms unless they have a very high efficiency.
To illustrate the problem here are some pictures:

The initial polygon is like this:

Integral polygon

An allowed sub-divison

A valid Integral Subdivison

An invalid sub-divison

Not a Valid Integral Subdivison

Thank you in advance.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is P convex? What is an integral sub-polygon? What is a polygonal division? Perhaps you should clarify... $\endgroup$
    – Aryabhata
    Commented May 7, 2015 at 23:09
  • $\begingroup$ 1. Please edit the question with clarifications, as suggested by Aryabhata. 2. In addition, what have you tried? There seems to be a straightforward recursive algorithm: it might inefficient, but it will be simple and meet your requirements. We expect you to make a significant effort on your own before asking, and to show us in the question what you've tried. $\endgroup$
    – D.W. ♦
    Commented Jun 5, 2015 at 0:51

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.