The are several NP-complete problems related to the construction of orthogonal polygons. Rapport showed that it is NP-complete to to decide the existence of orthogonal simple polygon that passes through given grid points (polygon’s vertices) such that the angles at those points are either 90, 270 or 180 degrees.

I’m interested in non-simple polygons (it may cross itself ). Given angles sequence at the vertices (left= 90 degrees or right=270 degrees) and crossings count, Is it NP-complete to decide the existence of orthogonal polygon with given angle sequence and crossings count?

P.S. Posted on MathOverflow



Your Answer

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