One way to look at the region segmentation problem is as a learning task: to classify the areas of the parameter space that have more of one class than the other. Hence one obvious way to segment the region is to use a segmenter that subdivides the parameter space appropriately.
One obvious learner that would do this is an axis-orthogonal decision tree builder, like C4.5 or J48. However, it is unlikely that we would want to use the full depth of the tree: this would generate as many regions as there are leaf nodes. However, if we were to enforce some heavy pruning regime (for example, requiring that no leaf node contain less than 5 per cent of the instances), this would essentially segment the parameter space into hypercubes; each representing region. Hence, rather than a Voronoi tiling applying, instances would be evaluated as to their presence in different regions of the parameter space.
This would require some other minor changes to the algorithm; for instance, the region membership. Furthermore, making the definitions comprehensible would require some work - one alternative is simply to give the description of the hypercube, but this may be inappropriate or not provide enough information into what is actually happening.