added 173 characters in body; deleted 175 characters in body
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.
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.