Basically, I'm interested in doing 2 things. Let's say we have a mesh M.
1. Find the minimum number of points(inside M) required to see the whole M.
2. Decompose M into polyhedrons which can be seen by only one point inside of them.
There are many articles on 2, for example I've found algorithms on convex decomposition of an object. I can surely use such algorithms but I need to have this ready in a sort amount of time and I think I can benefit from 1 and solve 2 very easily.
Let's say solution of 1 gives that the minimum number is N. The solution I'm thinking of requires finding the visibility of these N points, meaning I already have the parts of the object each of these points can see.
Having these parts I can easily construct the visible object from each point, excluding overlapping parts, therefore getting a minimum decomposition for my object.
My main concern is my solution for the first problem. I can't find anything on this online. I did find adequate information on the 2D art gallery problem but not on this. My only idea is to take samples of points in the object and do the following :
First I find the visibility polyhedron of every point inside the object ( that is the part of the object I can see).
Then for every combination of these points I combine their visibility polygons and see if their union forms M. The union with the least number of points is my solution.
Inspecting all the combinations is heavy obviously.I can save time starting from some upper bound but that is not the point. Is there a faster or less "brute force" approach?