2 Linear algebra

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.

1

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.