Random Testing (RT) is a fundamental technique of software testing. Adaptive Random Testing (ART) has recently been developed as an enhancement of RT that has better fault detection effectiveness. Several methods (algorithms) have been developed to implement ART. In most ART algorithms, however, the above enhancement diminishes when the dimensionality of the input domain increases. In this paper, we investigate the nature of failure regions in high dimensional input domains and propose enhanced random testing algorithms that improve the fault detection effectiveness of RT in high dimensional input domains.