In this paper, we address the problem of constrained segmentation of natural images, in which a human user places one seed point inside each object of interest in the image and the task is to determine the object boundaries. For this purpose, we study the connection between seed-based and hierarchical segmentation. We consider an Ultrametric Contour Map (UCM), the representation of a hierarchy of segmentations as a real-valued boundary image. Starting from a set of seed points, we propose an algorithm for constructing Voronoi tessellations with respect to a distance defined by the UCM. As a result, the main contribution of the paper is a method that allows exploiting the information of any hierarchical scheme for constrained segmentation. Our algorithm is parameter-free, computationally efficient and robust. We prove the interest of the approach proposed by evaluating quantitatively the results with respect to ground-truth data.