I have some code where the "hot part" relies on an inefficient solution to this problem.
Problem: I have 3 inputs:
a. A collection of N points on the surface of a sphere.
b. A line segment on the sphere.
c. A distance X (distance can be on the surface or in 3D as it's trivial to map between them)
Output: Find the subset of the line segment which is more than distance X from the collection of points.
(My problem actually involves a curve on the sphere, but I can reduce it to a line segment by chopping it up into smaller pieces.)
At present, I parametrize the line and created a distance function, subtract X then slam it into a method that finds the times when a function is positive. VERY slow.
Also, precomputations count in this algorithm. That is, the set does change over time, but it changes less frequently than I need this result for different line segments. Maybe 5 queries to every set change? That's worst case.
X is fixed over time.