I seem to recall to have read about Thiessen polygons which, instead of having straight boundaries, had some irregularly shaped sides. That was since those polygons were actually taking into account the terrain's slope. Did anyone come across something like that?
Thiessen polygons are defined as the set of points that are closer to a given site than to any other site. Usually, the distance is an Euclidian distance, which yields the straight lines of the most familiar Thiessen polygons. However, it can be generalized to other distance metric, in which case you don't end up with the same lines, of course. In GIS, distances such as Mahalanobie or Manhattan are not commonly used, but cost distance analysis are more frequent. You example with terrain's slope would be a special case of cost distance analysis. It is called cost allocation in most softwares, but note that 1) this is then a raster analysis and not something you can solve easily directly with vectors and 2) not all algorithm take the orientation of the slope into account to create the cost allocation.