Algorithm for Tailoring via Sculpting

Joseph O’Rourke () and Costin Vîlcu ()
Additional contact information
Joseph O’Rourke: Smith College
Costin Vîlcu: Romanian Academy

Chapter Chapter 6 in Reshaping Convex Polyhedra, 2024, pp 71-76 from Springer

Abstract: Abstract 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.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-031-47511-5_6

Ordering information: This item can be ordered from
http://www.springer.com/9783031475115

DOI: 10.1007/978-3-031-47511-5_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().