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

Question

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.

Answer 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.

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

Answer 2

If the querying aspect is important for you (i.e the lines keep appearing), then you should really build a data structure on the disks. Here's what you need to do. You need to build the arrangement on disks of radius X centered at each point (the arrangement being the way in which the sphere is decomposed into patches by the boundaries of the disks). Then, a point location query for each endpoint locates the start and end cells, and walking through the arrangement along the line gives you the subset of the line not covered by the disks.

While this is overkill for a single line (and Harald's solution is fine), it'll be more efficient if the lines are short and there are many of them (since the point location queries will run in time logarithmic in the number of points, and you hopefully won't have to walk through too many cells). To implement this is a little tricky though: luckily, CGAL has packages that you can use for this purpose. A source paper on this topic is here.