Protected: Vert-Solve Running Time

I’m interested in the running time of Poly-Solve and Vert-Solve. First note that because Poly-Solve and Vert-Solve use the same combinatorial approach they have the same big O running time.

Because I gave a more detailed listing for Vert-Solve, I’ll analyze Vert-Solve’s running time. For clarity I’ve reposted the Vert-Solve algorithm below.

function vert_solve(P = {set of puzzle pieces}, s = silhouette)
if P == ∅: return true

for (&p, v), w ∈ Pxs:
#By x I mean the Cartesian product, so (&p, v), w varies over all possible vertex pairs from P and s.

  g=position_vertex_pair((&p, v), w) #create a generator to position the vertex, v, so that it coincides with w, that is translate p so that v and w have the same coordinates. Note that there are several possible orientations of v‘s line segments (that’s why a generator is used).
    P’ = Pp #remove puzzle piece p from the set of puzzle pieces.

   while g.next_orientation() == true: #continue loop, until all valid (by valid I mean p is a subset of s) possible orientations of v‘s lines segments are exhausted.
          s’ = s\p #subtract puzzle piece p from shape s and set s’ equal to the shape resulting from the subtraction.

           if vert_solve(P’, s’) == true: return true
end for
return false

Let n = |P| + |s|, where |x| means the number of line segments of polygon x.
Note that the number of line segments is at most 2 * number of vertices.
For the set P, |P| means the total number of line segments for all the polygons in P.

Part A.

1. Let R(n) denote the running time of vert-solve for an input with n line segments i.e. n = |P| + |s|.

2. |Pxs| ≤ n2.

3. position_vertex_pair((&p, v), w) takes O(1) time, since it only creates a generator.

4. P’ = P – p, takes O(n) time (simply scan through the list P looking for vertices of p).

5. g.next_orientation() is the same algorithm as match_vertices which I gave in my post on 2D Geometric Algorithms. The the running time for match_vertices is O(m4), where m = |p| + |s| ≤ n. Because we’re doing big O running time I’ll let m = n, so g.next_orientation() takes O(n4) time.

6. s’ = s\p takes O(n3), see my post on 2D Geometric Algorithms for the running time analysis. Note that |s’| ≤ |s| – 3.

7. The running time for vert_solve(P’, s’) is R(n – 1) since |P’| + |s’| must be at least one smaller than |P| + |s|. This is because we’ve removed |p| line segments from P and added at most |p| – 1 line segments to s.

Part B. The while loop given by 5 runs at most n times and each loop takes n4 + n3 + R(n – 1) time. So the total time is
n^5 + n^4 + n\cdot R(n - 1).

The for loop given by 2 runs at most n2 times, so the total time is R(n) = n^2 \cdot (O(1) + n + n^5 + n^4 + n\cdot R(n - 1). Which simplifies to R(n) = n^7 + n^3R(n-1) (we only care about big O running time so the lower terms get absorbed into the n^7 term). Expanding yields n^7 + n^3(n-1)^7 + n^3(n-1)^3(n-2)^7 + \ldots + (n!)^3 \cdot 1^7 which is \le n^7 + n^3n^7+(n(n-1))^3n^7+\ldots + (n!)^3n^7 which equals n^7(1+n^3+(n(n-1))^3 + \ldots + (n!)^3), which is \le n^7(1 + n \cdot (n!)^3) \le n^7 + n^8 \cdot (n!)^3.

Thus the total running times is O(n^8{n!}^3). Hopefully I can improve this to exponential because n^8{n!}^3 is terrible!


One thought on “Protected: Vert-Solve Running Time

  1. Hello!

    First, i’m greatly impressed by your work and globally by your blog.
    I would like to do the same but in Prolog, i don’t know if you know it, it’s a logical language designed for Articifal Intelligence.
    I would like to know which book helped you to solve Tangram issue, or in the best case, if you can scan me some interesting pages of this book to help me for my project.
    I’m mostly interested by low-level features, such as mathematic, algorithmic and’subnet’ stuff.
    Your solution is, frankly, too hot for me :p

    I hope you’ll see my request.

    Thanks for any help Bryan!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s