How to treat undefined input space in supervised learning algorithms?
It depends on the machine learning technique. The following link gives a really good example comparing many classifiers and their segregation area. The same happens with clustering methods.

Classifier comparison