Adaptive Random Testing (ART) is a method for improving the fault-finding effectiveness of random testing. Fixed- Size Candidate Set ART is the most studied variant of this approach. However, existing implementations of FSCS-ART have had substantial selection overhead, with n test cases requiring O(^2) time to generate. We describe the use of a geometric data structure known as the Voronoi Diagram to reduce this overhead to no worse than O(nvn) and, with further optimization, O(n log n). We demonstrate experimentally that practical improvements in selection overhead can be gained using this improved implementation.