Segmentation of anatomical structures in medical imagery is a key step in a variety of clinical applications. Designing a generic, automated method that works for various structures and imaging modalities is a daunting task. In this paper, we present an effective interactive segmentation method that reformulates the GrowCut algorithm as a clustering problem and computes a fast, approximate solution. The method is further improved by using an efficient updating scheme requiring only local computations when new user input becomes available, making it applicable to high resolution images. The algorithm may easily be included as a user-oriented software module in any number of available medical imaging/image processing platforms such as 3D Slicer. The efficiency and effectiveness of the algorithm are demonstrated through tests on several challenging data sets where it is also compared to standard GrowCut.