CGAL users discussion list

[diethelm <>]

Dear all,

I hope this forum is the right place to ask my question. If not, I would
appreciate any pointers to the correct place.

My problem is that I want to compute Minkowski sums of two simple but
non-convex polygons P and Q, say, with m and n vertices, respectively. The
polygons are actually simply connected, i.e. there are no holes. Classical
knowledge tells me that the usual algorithms solve this problem in O((mn)^2)
time. Now my particular interest is in the two special cases where P = Q and
P = -Q. Thus, a straightfoward application of the standard algorithm gives a
method that has an O(n^4) complexity. Is there an algorithm for these two
special cases, or at least for one of them, that has a lower complexity?

Many thanks for your help.

Kai Diethelm 



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/fast-algorithm-for-special-case-of-2D-Minkowski-sums-tp4656437.html
Sent from the cgal-discuss mailing list archive at Nabble.com.