Abstract: We present a robust search for distance extrema from a point to a curve or a surface. The robustness comes from using geometric operations rather than numerical methods to find all local extrema. Tangent cones are used to search for regions where distance extrema conditions are satisfied and patch refinement hierarchically improves the search. Instead of preprocessing and storing a large hierarchy, elements are computed as needed and retained only if useful. However, for spatially coherent queries, this provides a significant speedup.