<p>Bayesian optimization (BO) offers an elegant approach for efficiently optimizing black-box functions by sequentially choosing the most favorable point according to an acquisition criterion. However, acquisition criteria demand their own challenging inner-optimization, which can induce significant overhead. Many practical BO methods, particularly in high dimension, eschew a formal, continuous optimization of the acquisition function and instead search discretely over a finite set of candidates which are in some sense representative. Here we propose candidates which lie on the boundary of the Voronoi tessellation of the current design points, such that they are equidistant to two or more of them. We discuss strategies for efficient implementation by directly sampling the boundary without explicitly generating the tessellation, thus accommodating large designs in high dimension. On a battery of test problems optimized via Gaussian processes with expected improvement, our proposed approach demonstrates significantly reduced execution time relative to a multi-start continuous search while retaining or even improving accuracy on most examined test problems. This has the potential to expand the class of problems on which BO is feasible.</p>