CODEWITHSUNDEEP
c++algorithmmathvector
kbirk
kbirk

Reputation: 4022

Reducing a minkowski difference to only its hull vertices?

Let's say we have two polyhedra, is there any effcient means of calculating only the vertices that are on the hull of the minkowski difference?

I know to get a single hull vertex you find the farthest vertex on one polyhedra in direction A and then the farthest vertex on the other in direction -A. But to do that for each and every vertices would be at least O(N^2). Is there a more efficient way?

Upvotes: 3

Views: 972

Answers (1)

n. m. could be an AI
n. m. could be an AI

Reputation: 120059

There's an efficient method of calculating the Minkowski sum (and hence also the difference) of convex polyhedra. It is described e.g. here. It is linear in terms of number of edges of the two polyhedra.

Since for any point-sets the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls, you can calculate the convex hulls first (with Chan's algorithm) and then do the Minkowski summation.

Upvotes: 3

Related Questions