محبوس‌کردن چندضلعی‌های نادقیق با استفاده از دو انگشت

نویسندگان
منصور داودی‌منفرد 1
اسماعیل دلفرازپهلوانلو 2
سیدمقداد نبوی‌لاریمی 2
1 استادیار، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه، زنجان، ایران
2 دانش آموخته کارشناسی ارشد، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه، زنجان، ایران
چکیده
یکی از مسائل کاربردی در حوزه روبوتیک، مسئله محبوس‌کردن یک شی دلخواه است. تمامی الگوریتم‌های مطرح در این زمینه فرض می‌کنند که شی دقیق باشد ولی به دلیل وجود خطا در محاسبات و ساخت اشیا این فرض می‌تواند اشتباه باشد و شی موردنظر تا حدودی نادقیق باشد. هدف ما ارائه راهکاری مناسب برای محبوس‌کردن یک چندضلعی با رئوس نادقیق است. در این مقاله الگوریتمی برای یافتن تمام موقعیت‌های دو نقطه که به طور قطع چندضلعی نادقیق را محبوس می‌کند، ارائه می‌دهیم و نشان می‌دهیم این الگوریتم تمام مجموعه‌های محبوس‌کننده را در زمان  On2logn  و فضای On2  گزارش می‌دهد که n  تعداد رئوس چندضلعی نادقیق است.

کلیدواژه‌ها

  • [1] M. Vahedi, Caging polygons with two and three fingers, Dept of Information and Computing Science, Utrecht University, 2009.
  • [2] W. Kuperberg, "Problems on polytopes and convex sets," DIMACS Workshop on polytopes, pp. 584-589 1990.
  • [3] A. S. Besicovitch, "A net to hold a sphere," Mathematical Gazette, vol. 41, no. 336, pp. 106-107, 1957.
  • [4] GC. Shephard, "A sphere in a crate," Journal of the London Mathematical Society, vol. 1, no. 1, pp. 433-434, 1965.
  • [5] P. Pipattanasomporn, and A. Sudsang. "Two-finger caging of concave polygon." In Proceedings 2006 IEEE International Conference on Robotics and Automation, ICRA, pp. 2137-2142, 2006.
  • [6] M. Vahedi, and A. F. van der Stappen, "Caging polygons with two and three fingers," The International Journal of Robotics Research, vol. 27, no. 11-12, pp. 1308-1324, 2008.
  • [7] P. Pipattanasomporn, and A. Sudsang, "Object caging under imperfect shape knowledge," In 2010 IEEE International Conference on Robotics and Automation, pp. 2683-2688, 2010.
  • [8] A. A. Requicha, "Toward a theory of geometric tolerancing," The International Journal of Robotics Research, vol. 2, no. 4, pp. 45-60, 1983.
  • [9] H. B. Voelcker, "A current perspective on tolerancing and metrology," International Forum on Dimensional Tolerancing and Metrology, New York, vol. 27, pp. 49-60. 1993.
  • [10] B. R. Donald, "Error detection and recovery in robotics," Berlin: Springer, vol. 336, 1989.
  • [11] S. M. LaValle, and S. A. Hutchinson, "An objective-based framework for motion planning under sensing and control uncertainties," The International Journal of Robotics Research, vol. 17, no. 1, pp. 19-42, 1998.
  • [12] M. Dogar, and S. Srinivasa, "A framework for push-grasping in clutter," Robotics: Science and systems, volII. 1, 2011.
  • [13] M. Löffler, "Data imprecision in computational geometry," PhD diss, Utrecht Univesity, 2009.
  • [14] M. Davoodi, and A. Mohades, "Data imprecision under λ-geometry model: Range searching problem," Scientia Iranica, vol. 20, no. 3, pp. 663-669, 2013.
  • [15] M. Davoodi, A. Mohades, F. Sheikhi, and P. Khanteimouri, "Data imprecision under λ-geometry model," Information Sciences, vol. 295, pp. 126-144, 2015.
  • [16] F. Panahi, M Davoodi, and A. F. van der Stappen, "Orienting parts with shape variation," IEEE Transactions on Automation Science and Engineering, vol. 14, no. 2, pp 1109-1118, 2015.
  • [17] J. Hershberger, and S. Suri. "A pedestrian approach to ray shooting: Shoot a ray, take a walk," Journal of Algorithms, vol. 18, no. 3, pp 403-431, 1995.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 2
پاییز و زمستان
پاییز 1398