2

It's been a while, that I'm searching some information about this problem.

Suppose we have some irregular $3D$ shape, the problem is to give an algorithm, to find exactly 1 nested basic shape, which has maximal volume among all other possibilities.


Saying basic shape, I mean - cube, cylinder, sphere, etc.
example of nested basic 3D shape

Google pointed me to some $2D$ analog problems. It seems to be, this problem is highly related with packing(nesting) problems. Some related SO links below.

Computational complexity and shape nesting
Best nesting algorithm
Nesting maximum amount of shapes on a surface

And according to answers, these class of problems seems to be at least NP complete. Anyways, I did not get the full picture, and left with few questions.

  • I was hoping to find a simple solution, maybe I shouldn't have complicated problem this far, and there's a really simple solution?
  • What kind of approaches could be "best" for this particular problem to use?
  • Maybe I'm digging in wrong direction? (packing problems are not related)

Any kind of references and readings are much appreciated. thank you

Community
  • 1
shcolf
  • 1,018
  • 2
    This is a difficult problem, even in 2D. See "Finding the Maximum Area Parallelogram in a Convex Polygon" for a start: PDF download. – Joseph O'Rourke Nov 16 '16 at 12:54
  • 1
    Thanks for your clarification, sir. After reading the paper you sent me, I guess I'll give up the idea of constructing direct algorithm. What do you think about continuing my further research in genetic algorithms? Is it able to solve the problem with some precision in reasonable time? – shcolf Nov 16 '16 at 15:14
  • @JosephO'Rourke thank for the answer - I am interested too. Is genetic algorithm the right path to follow? – Narek Nov 17 '16 at 06:44
  • Finding the largest sphere inside a convex polyhedron can be solved by linear programming. – Joseph O'Rourke Nov 17 '16 at 12:31

0 Answers0