Computational Problems on Depth Measures Combining Combinatorics and Geometry