Abstract: In Robotic Skull-Base Surgery, a surgical navigation and planning station is used to plan the path to be taken by the bone removal tool which is carried by a robotic manipulator. In planning for such a path, considerations have to be taken in terms of the manipulator characteristics and the geometric properties of the bone removal tool used. Presented in this paper is a methodology which takes into account the required efficacy of surgical planning. Differing from other surgical planning methodology, the final output of the planned surgery can be directly executed by a surgical robot (NeuRobot). In doing so, the surgeon has only to specify the region or features within the skull-base which are to be avoided and the general direction of action which specifies the eventual path that the surgery is to be carried out. A novel approach is taken by the use of Voronoi maps to identify "safe" cavities on each image slice.