2
$\begingroup$

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!

$\endgroup$

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.