GPU BASED PARALLEL ALGORITHM TO SOLVE LARGEST EMPTY RECTANGLE PROBLEM IN DISCRETE DOMAIN

摘要

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.