1
$\begingroup$

As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any algorithms or even anything theoretical to study on this problem online. The closest I found is decomposition to the minimum number of convex polygons.

Any suggestions as to how I should approach the problem?

I've tried to think about it by myself but the combinations seem too many and I don't want to get into writing an algorithm while my main problem is still unsolved.

Improve this question
$\endgroup$
4
  • $\begingroup$ Seems an open problem. This paper introduces an algorithm for decomposition without Steiner point. $\endgroup$ – xskxzr Apr 21 '18 at 17:02
  • $\begingroup$ @xskxzr Yes, Keil's algorithm is just what I need. I come across his name everywhere but I was hoping I wouldn't have to pay for an article. $\endgroup$ – John Katsantas Apr 21 '18 at 17:06
  • $\begingroup$ @xskxzr Do you know if the minimum star-shape number with Steiner points would be the same as without Steiner points? $\endgroup$ – John Katsantas Apr 21 '18 at 19:28
  • $\begingroup$ To be honest, I don't know. $\endgroup$ – xskxzr Apr 22 '18 at 3:39

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.