Supervised deep learning crucially depends on large amount of high-quality annotation data. While labeling for classification and grading tasks is rather efficient to achieve, labeling for segmentation is much more difficult and time-consuming, characterized by pixel-based dense annotation in practice. This approach suffers from two fundamental disadvantages: 1) Lack of efficiency because of the large number of pixels on region boundaries (other parts of an image can be easily labeled) and more importantly the need of precise positioning of boundary pixels. 2) Lack of certainty. The area around the boundaries is in fact the part of an image, where even medical experts are often uncertain and may make non-precise annotations, resulting in varying annotations by different experts (the serious problem of inter-observer variability). To overcome these disadvantages, we propose superpixel-based annotation instead of pixels. Importantly, we do not require to label in the area of boundaries with high uncertainty for medical experts. We automatically fill the unlabeled area (boundary gap). In addition to heuristic rules we also study the random walker. Experiments were conducted with three different medical segmentation tasks and two network models. Despite the easy-to-make sparse annotation we are able to achieve segmentation results that are comparable or even superior to those obtained by using pixel-based dense annotation. In addition to the high efficiency, our approach substantially reduces the inter-observer variability as a positive side effect.