Subject: CGAL users discussion list
List archive
- From: Efi Fogel <>
- To:
- Subject: Re: [cgal-discuss] fast algorithm for special case of 2D Minkowski sums?
- Date: Thu, 3 Jan 2013 14:13:43 +0200
Given two concave polygons P and Q, the complexity of the Minkowski sum (the structure itself) M = P + Q is O(n^2m^2). This bound is tight.
The complexity of constructing M depends on the alg. and can be done in O(n^2m^2 log nm).
I think that it is possible to come up with a concave polygon P', such that the complexity of the Minkowski sum M' = P' + P' is O(n^4). Take the two concave polygons P and Q the Minkowski sum of which has complexity O(n^2m^2) and somehow unify them into P'. I believe that the same holds for a polygon P'', P'' + -P''... If I'm right, you are, theoretically speaking, out of luck, but typically the complexities are much smaller.The complexity of constructing M depends on the alg. and can be done in O(n^2m^2 log nm).
On Thu, Jan 3, 2013 at 12:59 PM, diethelm <> wrote:
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.
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss
--
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
- [cgal-discuss] fast algorithm for special case of 2D Minkowski sums?, diethelm, 01/03/2013
- Re: [cgal-discuss] fast algorithm for special case of 2D Minkowski sums?, Efi Fogel, 01/03/2013
Archive powered by MHonArc 2.6.18.