spherical geometry - Find the subset of a line on a sphere "far" from a set of points on the sphere.

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.