Incremental Construction of Generalized Voronoi Diagrams on Pointerless Quadtrees
المؤلفون المشاركون
Yin, Quanjun
Qin, Long
Liu, Xiaocheng
Zha, Yabing
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-14، 14ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-02-26
دولة النشر
مصر
عدد الصفحات
14
التخصصات الرئيسية
الملخص EN
In robotics, Generalized Voronoi Diagrams (GVDs) are widely used by mobile robots to represent the spatial topologies of their surrounding area.
In this paper we consider the problem of constructing GVDs on discrete environments.
Several algorithms that solve this problem exist in the literature, notably the Brushfire algorithm and its improved versions which possess local repair mechanism.
However, when the area to be processed is very large or is of high resolution, the size of the metric matrices used by these algorithms to compute GVDs can be prohibitive.
To address this issue, we propose an improvement on the current algorithms, using pointerless quadtrees in place of metric matrices to compute and maintain GVDs.
Beyond the construction and reconstruction of a GVD, our algorithm further provides a method to approximate roadmaps in multiple granularities from the quadtree based GVD.
Simulation tests in representative scenarios demonstrate that, compared with the current algorithms, our algorithm generally makes an order of magnitude improvement regarding memory cost when the area is larger than 210×210.
We also demonstrate the usefulness of the approximated roadmaps for coarse-to-fine pathfinding tasks.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Yin, Quanjun& Qin, Long& Liu, Xiaocheng& Zha, Yabing. 2014. Incremental Construction of Generalized Voronoi Diagrams on Pointerless Quadtrees. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-14.
https://search.emarefa.net/detail/BIM-472964
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Yin, Quanjun…[et al.]. Incremental Construction of Generalized Voronoi Diagrams on Pointerless Quadtrees. Mathematical Problems in Engineering No. 2014 (2014), pp.1-14.
https://search.emarefa.net/detail/BIM-472964
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Yin, Quanjun& Qin, Long& Liu, Xiaocheng& Zha, Yabing. Incremental Construction of Generalized Voronoi Diagrams on Pointerless Quadtrees. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-14.
https://search.emarefa.net/detail/BIM-472964
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-472964
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر