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.



Find the subset of a line on a sphere "far" from a set of points on the sphere.
By a line on the sphere, I assume you mean a part of a great circle spanning less than 180°.


For each of the *N* points, find what part of the line is closer than *X* to that point. This is at most a single segment. Find their union *C* as a disjoint union of segments. This is probably easier if you sort them by their starting point, and the obvious algorithm gives you the union as a sorted list as well – which makes the last part trivial: Find the complement of *C*.


Oh, and the first part can be done with some simple linear algebra.


