Efficient and effective random testing using the Voronoi Diagram

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(n 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(n-√n) and, with further optimization, O(n log n). We demonstrate experimentally that practical improvements in selection overhead can be gained using this improved implementation.