Cell-based lattice-free simulations of the growth of tumor tissues require the definition of geometrical and topological relations among cells and the other basic elements of the simulation (most notably the local and the global environments). This is necessary for the correct description of the biochemistry of tumor tissues, and to implement the biomechanical interactions among cells. Weak cell-cell forces and the necrosis of tumor tissues due to poor vascularization can lead to the formation of cavities - i.e., regions without viable cells and filled with cellular debris and fluids. It is important to give an accurate geometrical/topological description of the resulting microenvironment that plays an important role in the pathology of cancer. In this paper, we concentrate on simulations of the growth of avascular solid tumors and we describe the STAR (Shape of Tumors from Algorithmic Reconstruction) algorithm that defines the shape of clusters of cells and searches for the boundary and cavities in a 3D environment. The algorithm is GPU-based and exploits the high degree of parallelism of GPUs. The final implementation achieves a 30-fold speedup with respect to a previous CPU-based version.