Skip to main content
MathOverflow

Return to Question

added a top-level tag; see: https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as the outer boundary. The problem is finding the 3D polygon that fits only within the inner and outer boundaries with the minimum number of facets/vertices. At maximum error, a tetrahedron would be the resulting polygon, at minimum error it would be the original convex hull. As a 2D problem, I can see how it would be straightforwardsstraightforward to make a brute force method of calculating this, but the 3D aspect throws me completely. Can anyone give any pointers as to how this can be solved, or if there is any software that can do this already?

I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as the outer boundary. The problem is finding the 3D polygon that fits only within the inner and outer boundaries with the minimum number of facets/vertices. At maximum error, a tetrahedron would be the resulting polygon, at minimum error it would be the original convex hull. As a 2D problem, I can see how it would be straightforwards to make a brute force method of calculating this, but the 3D aspect throws me completely. Can anyone give any pointers as to how this can be solved, or if there is any software that can do this already?

I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as the outer boundary. The problem is finding the 3D polygon that fits only within the inner and outer boundaries with the minimum number of facets/vertices. At maximum error, a tetrahedron would be the resulting polygon, at minimum error it would be the original convex hull. As a 2D problem, I can see how it would be straightforward to make a brute force method of calculating this, but the 3D aspect throws me completely. Can anyone give any pointers as to how this can be solved, or if there is any software that can do this already?

Source Link
Robin Weert
Robin Weert
  • 21
  • 2

Minimal vertices 3D polygon fitting between inner and outer boundaries

I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as the outer boundary. The problem is finding the 3D polygon that fits only within the inner and outer boundaries with the minimum number of facets/vertices. At maximum error, a tetrahedron would be the resulting polygon, at minimum error it would be the original convex hull. As a 2D problem, I can see how it would be straightforwards to make a brute force method of calculating this, but the 3D aspect throws me completely. Can anyone give any pointers as to how this can be solved, or if there is any software that can do this already?