Incremental Construction of Generalized Voronoi Diagrams on Pointerless Quadtrees

• DOI: 10.1155/2014/456739
• Publication Date: 2014-03-03T07:57:38Z
• Authors: Quanjun Yin; Long Qin; Xiaocheng Liu; Yabing Zha
• Keywords: 0209 industrial biotechnology; 02 engineering and technology

In robotics, Generalized Voronoi Diagrams (GVDs) are widely used by mobile robots to represent the spatial topologies of their surrounding area. this paper we consider problem constructing GVDs on discrete environments. Several algorithms that solve exist in literature, notably Brushfire algorithm and its improved versions which possess local repair mechanism. However, when area be processed is very large or high resolution, size metric matrices these compute can prohibitive. To address issue, propose an improvement current algorithms, using pointerless quadtrees place maintain GVDs. Beyond construction reconstruction a GVD, our further provides method approximate roadmaps multiple granularities from quadtree based GVD. Simulation tests representative scenarios demonstrate that, compared with generally makes order magnitude regarding memory cost larger than<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M1"><mml:msup><mml:mrow><mml:mn>2</mml:mn></mml:mrow><mml:mrow><mml:mn>10</mml:mn></mml:mrow></mml:msup><mml:mo>×</mml:mo><mml:msup><mml:mrow><mml:mn>2</mml:mn></mml:mrow><mml:mrow><mml:mn>10</mml:mn></mml:mrow></mml:msup></mml:math>. We also usefulness approximated for coarse-to-fine pathfinding tasks.