A revisit to the planar subdivision graph: free space detection in a dynamic environment with polygonal obstacles

A common requirement for the robot motion planning problem is to find the free space for a given map with polygonal obstacles. If the map changes dynamically where obstacles are inserted or deleted consequently, the free space needs to be updated. In this work, we propose an algorithm based on a planar subdivision graph of a dynamically changing map and consequently detect the changing of its free space. The algorithm represents each vertical slab as a specially designed tree containing trapezoids. These trees can be easily updated or merged with other trees while inserting or deleting a polygon. The time complexity for updating the proposed data structure due to the insertion or deletion of a polygon is O(N), where N is the number of existing polygons.