GPU based Parallel Algorithm to Solve Largest Empty Rectangle Problem in Discrete Domain

S. Sitamraju and A. Shrivastava (India)


Parallel Processing, Largest Empty Rectangle, GPU


In this paper, we propose a simple parallel algoritm for solving the largest empty rectangle problem in discrete domain on a rectangular pixel grid. Our algorithm has a computational complexity of O(M+N) for a MxN grid. We implement the algorithm using CUDA programming language on GPU.

Important Links:

Go Back