Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for this NP-complete problem that was later also shown to be an 8/3-approximation algorithm for the general case.

I am currently looking for such an approximation algorithm for the 3-dimensional case, for the minimal covering of orthogonal polyhedra with cuboids (both for ones with and without holes). Is there a suitable solution?

Otherwise, my solution would be to extend Franzblaus algorithm for this case.

Thanks a lot for the help!


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.