Fitting a convex polytope into another convex polytope

In summary: Expert SummaryIn summary, the individual is seeking help with a Python code to fit a polytope with a given number of faces into another known polytope with more faces. Two formulations of the problem have been tried, but both have resulted in difficulties. Suggestions for different optimization methods, objective functions, polytope representations, and volume measures are offered to help find a solution.
  • #1
cr34m3
2
0
Hi,

I am presently writing Python code to solve the following problem; fit the largest volume polytope (P1), with a given number of faces, into a known other polytope (P2) (with more faces than the one being fitted inside). Both polytopes are convex and are described by the feasible region of a number of halfspaces, also both polytopes have the same number of dimensions.

The polytope, P1, is described by Ax < b. A halfspace description was favoured above a vertex description as the number of vertices do not have a clear correlation to the number of faces (which are to be specified). The solution would then be;
- Optimize for A and b, to
- maximise the volume of P1, subject to
- P1 inside of P2.

In the 2D case, this simplifies to; fit the largest triangle (P1) into a given square (P2).

Two formulations of the problem have been tried;
firstly, using a constrained solver (Sequential Least Squares Quadratic Programming) - this gives problems (especially when P1 inverts itself). The gradient information seems unreliable (noting that for a fixed size gradient matrix, the inequality constraints need to be expressed in terms of the initial shape P2).
Secondly, using an unconstrained solver (Downhill Simplex), reformulating the problem with penalties. Vertices are penalized when outside of the initial shape. This however places too much emphasis on the vertices and makes the solution a very strong function of the starting point. Vertices simply migrate to the edges of P2 without maximising P1's volume.

The problem seems rather straightforward, but I'm not making progress.

Any suggestions on problem reformulation or methods of solving this would be greatly appreciated.

André
 
Physics news on Phys.org
  • #2



Hi André,

Thank you for sharing your problem with us. It is certainly an interesting one and I can see why you are having some difficulty finding a solution. Here are a few suggestions that may help you in your quest to maximize the volume of P1 within P2:

1. Consider using a different optimization method. While the methods you have tried so far may not be yielding the desired results, there are many other optimization methods out there that may be better suited for your problem. For example, genetic algorithms or simulated annealing may be useful in finding a global maximum for your objective function.

2. Try using a different objective function. Instead of simply maximizing the volume of P1, you could consider incorporating penalties or constraints that take into account the shape of P1. This may help prevent P1 from inverting itself or migrating to the edges of P2.

3. Consider using a different representation for your polytopes. While a halfspace description may have been favored initially, it may not be the most suitable for this particular problem. You could try using a vertex description instead, as it may provide a clearer correlation between the number of vertices and the number of faces.

4. Look into other methods of measuring volume. Instead of simply using the traditional volume formula for your polytopes, you could consider using alternative measures of volume that may be better suited for your problem. For example, you could use the determinant of the covariance matrix of the points in P1 or P2 as a measure of volume.

I hope these suggestions help you make progress on your problem. Good luck!


 

FAQ: Fitting a convex polytope into another convex polytope

1. What is a convex polytope?

A convex polytope is a geometric shape that is defined by a finite number of points and line segments connecting those points. It is a convex shape, meaning that all of its internal angles are less than 180 degrees and any line segment connecting two points on the shape lies completely within the shape itself.

2. What does it mean to "fit" one convex polytope into another?

Fitting one convex polytope into another means finding a way to place the first polytope inside the second polytope so that all points of the first polytope lie within the second polytope. This can be accomplished by translating, rotating, and scaling the first polytope.

3. Why would someone want to fit one convex polytope into another?

Fitting one convex polytope into another can be useful in various applications, such as computer graphics, computer-aided design, and optimization problems. It can also be used to study the properties and relationships between different convex polytopes.

4. What techniques are used to fit one convex polytope into another?

The most common technique for fitting one convex polytope into another is called "linear programming" which involves finding the optimal solution to a set of linear equations and inequalities. Other techniques include using geometric transformations and algorithms specifically designed for fitting convex polytopes.

5. Are there any limitations or restrictions when fitting one convex polytope into another?

Yes, there are some limitations and restrictions when fitting one convex polytope into another. For example, both polytopes must be convex and have the same dimensionality. Additionally, the polytopes must not intersect or overlap in any way for a successful fit.

Similar threads

Replies
21
Views
8K
Replies
7
Views
2K
Replies
1
Views
3K
Replies
1
Views
3K
Replies
6
Views
4K
Replies
8
Views
3K
Back
Top