Texture Packing is to pack multiple rectangle shaped textures into one large texture. The resulting texture must have a given width and a minimum height.
This project requires you to design an approximation algorithm that runs in polynomial time. You must generate test cases of different sizes (from 10 to 10,000) with different distributions of widths and heights. A thorough analysis on all the factors that might affect the approximation ratio of your proposed algorithm is expected.
Grading Policy: Programming: Implement the approximation algorithm (6 pts.). Write a test of performance program (1 pts.). All the codes must be sufficiently commented.
Testing: Generate the test cases and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (5 pts.). The analysis must be based on your testing results.
Documentation: Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
Bonus: Compare your algorithm to any of the known strip algorithms.
Note: Anyone who does excellent job on answering the Bonus question will gain an extra point.