A new scheme for finding the biggest rectangle that doesn`t have any obstacle


The KIPS Transactions:PartA, Vol. 18, No. 2, pp. 75-80, Apr. 2011
10.3745/KIPSTA.2011.18.2.75,   PDF Download:

Abstract

Recently, many cleaning robots have been made with various algorithms for efficient cleaning. One of them is a DmaxCoverage algorithm which efficiently clean for the situation when the robot has a time limit. This algorithm uses Rectangle Tiling method for finding the biggest rectangle that doesn`t have any obstacle. When the robot uses grid map, Rectangle Tiling method can find the optimal value. Rectangle Tiling method is to find all of the rectangles in the grid map. But when the grid map is big, it has a problem that spends a lot of times because of the large numbers of rectangles. In this paper, we propose Four Direction Rectangle Scanning(FDRS) method that has similar accuracy but faster than Rectangle Tiling method. FDRS method is not to find all of the rectangle, but to search the obstacle`s all directions. We will show the FDRS method`s performance by comparing of FDRS and Rectangle Tiling methods.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. H. Hwang and H. S. Jeon, "A new scheme for finding the biggest rectangle that doesn`t have any obstacle," The KIPS Transactions:PartA, vol. 18, no. 2, pp. 75-80, 2011. DOI: 10.3745/KIPSTA.2011.18.2.75.

[ACM Style]
Jung Hwan Hwang and Heung Seok Jeon. 2011. A new scheme for finding the biggest rectangle that doesn`t have any obstacle. The KIPS Transactions:PartA, 18, 2, (2011), 75-80. DOI: 10.3745/KIPSTA.2011.18.2.75.