OBJECTIVE The purpose of this study is to investigate the role of the centroidal Voronoi tessellation (CVT) and constrained CVT (CCVT) in inverse planning in combination with the Hybrid Inverse Planning Optimization (HIPO) algorithm in HDR brachytherapy of prostate cancer. HIPO implemented in Oncentra© Prostate treatment planning system, is used for three-dimensional (3D)-ultrasound-based intraoperative treatment planning in high dose rate brachytherapy. HIPO utilizes a hybrid iterative process to determine the most appropriate placement of a given number of catheters to fulfil predefined dose-volume constraints. The main goals of the current investigation were to identify a way of improving the performance of HIPO inverse planning; accelerating the HIPO, and to evaluate the effect of the two CVT-based initialization methods on the dose distribution in the sub-region of prostate that is not accessible by catheters, when trying to avoid perforation of urethra. METHODS We implemented the CVT algorithm to generate initial catheter configurations before the initialization of the HIPO algorithm. We introduced the CCVT algorithm to improve the dose distribution to the sub-volume of prostate within the bounding box of the urethra contours including its upper vertical extension (U-P). For the evaluation, we considered a total of 15 3D ultrasound-based HDRBT prostate implants. Execution time and treatment plan quality were evaluated based on the dose-volume histograms of prostate (PTV), its sub-volume U-P, and organs at risk (OARs). Furthermore, the conformity index COIN, the homogeneity index HI and the complication-free tumor control probability (P+ ) were used for our treatment plan comparisons. Finally, the plans with the recommended HIPO execution mode were compared to the clinically used intraoperative pre-plans. RESULTS The plan quality achieved with CCVT-based HIPO initialization was superior to the default HIPO initialization method. Focusing on the U-P sub-region of the prostate, the CCVT method resulted in a significant improvement of all dosimetric indices compared to the default HIPO, when both were executed in the adaptive mode. For that recommended HIPO execution mode, and for U-P, CCVT demonstrated in general higher dosimetric indices than CVT. Additionally, the execution time of CCVT initialized HIPO was lower compared to both alternative initialization methods. This is also valid for the values of the aggregate objective function with the differences to the default initialization method being highly significant. Paired non-parametric statistical tests (Wilcoxon signed-rank) showed a significant improvement of dose-volume indices, COIN and P+ for the plans generated by the CCVT-based catheter configuration initialization in HIPO compared to the default HIPO initialization process. Furthermore, in ten out of 15 cases, the CCVT-based HIPO plans fulfilled all the clinical dose-volume constraints in a single trial without any need for further catheter position adaption. CONCLUSIONS HIPO with CCVT-based initialization demonstrates better performance regarding the aggregate objective function and convergence when compared to the CVT-based and default catheter configuration initialization methods. This improved performance of HIPO inverse planning is clearly not at the cost of the dosimetric and radiobiologically evaluated plan quality. We recommend the use of the CCVT method for HIPO initialization especially in the adaptive planning mode.