Algorithm for Tailoring via Sculpting

In this research we have also concentrated on achieving constructive proofs of the theorems, constructive in the sense of leading to finite algorithms. In this chapter we follow Theorem 4.6 to yield an algorithm for achieving the tailoringtailoringdigon- of P to Q. Denote by |P| the number of vertices of P. Throughout we measure computational complexity in terms of n, where n = max { | P | , | Q | } $$n=\max \{ |P|, |Q| \}$$ is the larger number of vertices of P or Q; so |P|, |Q| = O(n) (Recall that O(nk) means that the asymptotic time complexitytime complexity is upper-bounded by a polynomial in n of degree k. Later we will use Ω(nk) to indicate a lower bound.). Our goal for all the algorithms is to achieve polynomial-time complexity,time complexity O(nk), but we have not worked hard to lower k, through, e.g., exploitation of efficient data structures. Instead we are content to leave improvements for future work. We will see that k = 4 seems to suffice.