Loading...
Search
| Friend's email | |
| Your name | |
| Your email | |
| enter code | |
This page was sent successfuly
Digital Object List
Bookmark
Review List- Type of Document: M.Sc. Thesis
- Language: Farsi
- Document No: 44660 (02)
- University: Sharif University of Technology
- Department: Mathematical Sciences
- Advisor(s): Zarei, Ali Reza
- Abstract:
- This thesis is concerned with a fundamental problem in computational geometry. This problem inspects covering a space with a set of points provided that each point of the space is visible to at least one point from the selected subset. Applications of these problems are in the areas such as geographic information systems (GIS), robotics,computer graphics and the military.The investigated space is a planar rectangular region which is partitioned into smaller rectangles by connected edges. The objective of this study is to find an optimized corridor; i.e., a connected subset of edges which contains at least one point from each rectangle. For the minimum diameter corridor problem, an exact polynomial time algorithm and for the minimum length corridor problem, an approximation algorithm is presented
- Keywords:
- Computational Geometry ; Minimum Corridor Connection ; Corridors ; Approximate Algorithm
-
محتواي کتاب
- view
- سپاسگزاری
- چکیده
- فهرست تصاویر
- فهرست جداول
- فهرست الگوریتمها
- مقدمه
- مقدمه
- تعریف دقیق مساله
- ساختار پایاننامه
- یافتن راهرو با طول کمینه
- ربات تمیزکننده
- درخت پوشای کمینه تعمیمیافته حداقلی
- راهرو متعامد و مستطیلی با طول کمینه
- اثبات NP -تمام بودن مساله MLC که راهرو فقط اتاقها را پوشش میدهد
- اثبات NP -تمام بودن مسایل MLC و MLC-R
- الگوریتم تقریبی برای مساله MLC-R و MLC
- راهرو پوششی با قطر کمینه
- درخت پوشا با قطر کمینه
- یافتن مرکز مطلق یک گراف
- درخت اشتاینر با قطر کمینه
- درخت اشتاینر با قطر کمینه برای گراف دلخواه متریک
- مساله پوشش با قطر کمینه
- درخت پوشا با قطر کمینه
- یافتن راهرو با قطر کمینه برای ناحیه مستطیلبندیشده
- ایدههای اولیه
- الگوریتم یافتن درخت با قطر کمینه برای ناحیه مستطیلبندیشده
- الگوریتم یافتن راهرو با قطر کمینه
- درستی الگوریتم
- پیچیدگی الگوریتم
- بهبود زمان اجرای الگوریتم یافتن درخت با قطر کمینه برای ناحیه مستطیلبندیشده
- درستی الگوریتم
- پیچیدگی الگوریتم
- بهینه کردن راهرو از نظر طول
- الگوریتم تقریبی برای راهرو با طول کمینه برای ناحیه مستطیلبندیشده
- تعمیم روش ربات برای مشبکه
- اثبات NP -سخت بودن مساله MLC-R2
- الگوریتم تقریبی برای مساله MLC-R2
- کاهش مساله MLC-R به مساله MLC-R2
- الگوریتم تقریبی دیگر برای MLC-R2
- کاهش مساله MLC-R2 به مساله درخت اشتاینر
- تعمیم ایده الگوریتم تقریبی برای مساله MLC2
- نتیجهگیری و پیشنهادها
- مراجع