MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Very nice paper. That is kind of what I had in mind, but Harald's answer looks to be a lot easier to code, and probably is going to be good enough for me as long as X is large enough. (The exact final values of X are TBD.) THANKS! – John Mar 17 '10 at 22:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.