There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-Ottmann and Fortune's algorithm, but also things like Dijkstra's algorithm and Prim's algorithm.

There's no trivial way to parallelize these algorithms: In non-degenerate cases there's exactly one event which is legal to process. One could speculatively distribute the next n events to n processors, but (a) handling them in any interleaved order would generally violate the algorithm's invariants, and (b) would often add new events to the priority queue which should have been handled earlier.

Nevertheless, for things like sweep-line algorithms, there's a natural locality to exploit. Handling two events which are close to each other along the sweep axis but far away on the perpendicular axis would probably be okay as long as the underlying state structure could be concurrently updated, and one could imagine either speculatively handling those events and rolling back only when interactions were detected, and/or partitioning a prefix of the queue into mutually independent workloads.

Are there any articles which explore this sort of approach, either for specific problems or for paradigms like sweep-line algorithms?

  • $\begingroup$ For line segment intersection, you could try to parallelize the problem by dividing the sweep axis in parts and split segments that cross two different parts in pieces such that every part contains all endpoints of each segment or segment piece in that part. This can however lead to a lot of additional segments if your segments are long. $\endgroup$
    – Discrete lizard
    Jun 7 '19 at 13:09

Two old, but, I think, still very useful resources:

  • M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to what you are asking about, download for free: link.

  • S.G.Akl, K.A.Lyons. Parallel Computational Geometry. Prentice-Hall, 1993 - monograph about first ten years of research in parallel computational geometry. In the Chapter Four they say: "The plane sweep technique appears to be inherently sequential", but nevertheless refer to a number of parallel sweeping algorithms. Please see: link.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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