A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
4

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.


4

Every facet in a 3D convex hull has a normal vector. The key is to determine which facets have an outward normal vector pointing downward. You can determine this easily by looking at the z-component of each normal vector. If it is negative, it's part of the lower hull. If it's positive, it's part of the upper hull. Of course, you'll have to decide ...


3

If the dimension is not too high, you can use a triangulation library (e.g. CGAL) to decompose the polytope into n-dimensional simplices; calculating the volume of a simplex has a simple formula.


3

The set of convex sets is infinite dimensional, which is not amenable to computation. I would discretize this by replacing your solution set (consisting of all convex sets) by a finite dimensional set -- for example, polygons with $N$ vertices. This finite dimensional set can conveniently be represented as the intersection of $N$ half-spaces and you would ...


2

You're allowed an algorithm that computes the hull. If this means an algorithm that computes the convex polygon then I would say consider the lines defined by adjacent points on that polygon. I think it's possible to prove that one of those lines is the one required. Therefore, the required algorithm is simply to iterate through them, calculate sums of ...


1

Let the $x$-coordinates for the points in the convex hull of the first convex region be stored in the array x1, and let the $y$-coordinates of those same points be stored in the array y1. Let the arrays x2 and y2 store analogous information for the second convex region. If you have MATLAB's Mapping Toolbox, you can use the polybool function to return the ...


1

If you represent the set of paths as a set of individual line segments $S=\{L_k\}$ between consecutive points, then the intersection of the set you want with the line $x=x_0$ is between the lower-most and the upper-most intervals that contain the $x$-coordinate $x_0$. In particular, your set is bounded by a set of line segments whose endpoints lie only on ...


1

The most reputable-looking source I could find was M. E. Dyer, L. G. Proll. An algorithm for determining all extreme points of a convex polytope, Mathematical Programming, Vol. 12, Issue 1, p. 81-96. The problem is likely only solvable for the case of convex polyhedra; there is a theorem that states that convex polyhedra can be expressed in terms of a ...


Only top voted, non community-wiki answers of a minimum length are eligible