Hi Samuel,

Well I could be the first one to argue that it's too conservative ! At
least for my use case. My variant is populated by all the OGC types,
that is all the combinations (points, multilines, ...) * (xy, xyz, xym,

That's the kind of use case I had thought could indeed contradict that approach. I was just hoping it wouldn't come too soon :-)
I can't not think of a way to reduce this set to the acceptable
combinations for each algorithms, so believe I'll will have to deal with
runtime errors at the "default strategy resolution" stage, right ?

Nope, if a compile-time choice must be made about how to handle invalid algorithm invocation, IMO it has to be done within the "not_implemented" class itself. For compile-time failure, it would be just like it is now. For runtime failures, it would have to define a generic apply() function that throws.
Could the use of a "policy" to choose between the conservative (compile
time error) and the relaxed (runtime error) approaches be an option ?

That would be the ideal way to do I think. And "policies" are currently what we call "strategies". I'd like them to become more generic in the future, basically policy-based classes (aka mixins) e.g. user could pass "pythagoras_calculation() & calculation_type<double>() & runtime_error_handling()" as the strategy for distance() (or any one of them with a fallback on defaults for the rest). But we're not quite there yet and that's a long term goal. To support runtime errors in the meantime we could propose a more global way to do. I'll think about it.

What would be the algorithms you would need this for?