پرش به مطلب اصلی

هندسه محاسباتی

Computational Geometry​

نام درس:هندسه محاسباتیمقطع:کارشناسی
پیش‌نیاز:طراحی و تحلیل الگوریتم‌هاگروه درس:تخصصی اختیاری
هم‌نیاز:نداردنوع درس:نظری
تعداد واحد:3تعداد ساعت:48
حل تمرین:دارد

سرفصل درس:

  • پوسته‌ی محدب. محاسبه‌ی پوسته‌ی محدب در صفحه، عملیات پایه‌ی هندسی. چند روش برای محاسبه‌ی پوسته‌ی محدب در صفحه. الگوریتم‌های حساس به خروجی، دو الگوریتم بهینه از چن. پوسته‌ی محدب در فضای سه‌بعدی. پیچیدگی ترکیبیاتی، نحوه‌ی نمایش. الگوریتم تصادفی کلارکسون-شور. تقاطع و چینش خطوط. ساخت چینش خطوط. تقاطع پاره‌خط‌ها، الگوریتم جاروب صفحه. نمودار ورونوی و مثلث‌بندی. تعریف نمودار ورونوی و ویژگی‌ها. مثلث‌بندی دلونی و خواص آن، الگوریتم فورچیون. کاربردهای نمودار ورونوی و مثلث‌بندی دلونی.کوچک‌ترین دایره‌ی محیطی. مکان‌یابی نقاط. روش تقسیم و حل، نقشه‌ی ذوزنقه‌ای. مثلث‌بندی چندضلعی. کاربردهای مثلث‌بندی، مسئله‌ی گالری هنر.

منابع:

  • دی برگ، م.، چیونگ، اوتفرید، وان کریولد، م.، اورمارس، م. (۱۳۹۴). هندسه محاسباتی الگوریتم ها و کاربردها. (م. ایمان پرست، مترجم). تهران، ایران: دانش نگار.

  • Uehara, R. (2020). Introduction to Computational Origami. Springer.

  • Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer-Verlag.

  • O'Rourke, J. (1998). Computational Geometry in C (2nd ed.). Cambridge University Press.

  • Boissonnat, J.-D., & Yvinec, M. (1998). Algorithmic Geometry. Cambridge University Press.

  • Devadoss, S. L., & O'Rourke, J. (2011). Discrete and Computational Geometry. Princeton University Press.

  • Edelsbrunner, H. (1987). Algorithms in Combinatorial Geometry. Springer.

  • Goodman, J. E., O'Rourke, J., & Tóth, C. D. (Eds.). (2017). Handbook of Discrete and Computational Geometry (3rd ed.). CRC Press.

  • Har-Peled, S. (2011). Geometric Approximation Algorithms. AMS Press.

  • Demaine, E. (2020), MIT Course, Geometric Folding Algorithms: Linkages, Origami, Polyhedra, http://courses.csail.mit.edu/6.849/fall20/