# Parallelization of priority queue-based algorithms

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?

• 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. – Discrete lizard Jun 7 at 13:09