Purpose: Radiosurgical treatment planning requires a good approximation of the dose distribution which is typically computed on a high resolution grid. However, the resulting optimization problem is large, and leads to substantial runtime. We study a sparse grid approach, for which we estimate and compensate for the expected deviations from the bounds. Methods: We buildup an estimate of the hotspot error distribution by measuring the maximum dose deviation within a voxel for a large number of randomly generated beam configurations. This results in a conservative estimation of overdosage as a function of upper bound reduction for different grid sizes. We adjust the bounds for voxels inside the target volume (PTV) according to our estimation thus maintaining the likelihood of dose deviations within acceptable limits. The approach was applied to a prostate case, where the volumes of interest are large and close to each other. Our planning objective is a prescribed dose of 36.25 Gy to the 87% isodose. We employed constrained optimization to optimize the lower PTV bound on 2, 4, and 8mm isotropic grids. Results were computed on 1mm grid. Results: The initial coverage was 93.7%, 92%, and 91%, and the volume exceeding the upper bound was 0.74%, 1.71%, and 9% for grid sizes of 2, 4, and 8mm, respectively. Changing the upper bound by 0.5% and 2.5% for the 4 and 8 mm grids resulted in only 0.75% and 2.2% of the volume exceeding the bound. The coverage did not change. Mean optimization times were 141.1, 22.6 and 3.4 minutes using the 2, 4 or 8mm grid, respectively. Conclusions: Experiments show that planning on a sparse grid can achieve comparable results with those of a high resolution grid, as long as the bounds are carefully balanced. This leads to substantially lower optimization times which facilitates interactive planning. This work was supported by the Graduate School for Computing in Medicine and Life Sciences funded by Germanyâ€™s Excellence Initiative [DFG GSC 235/1].