Algorithm
Development Kit 1.0

Package algs.model.problems.segmentIntersection.priorityqueue

Defines the classes needed to implement the event queue using a priority queue that does not support searching.

See:
          Description

Class Summary
SlowEventQueue The EventQueue for a horizontal-sweep line algorithm for line segment intersection.
SlowLineSweep Uses slow event queue to show degradation of performance when using just a standard priority queue implementation.
 

Package algs.model.problems.segmentIntersection.priorityqueue Description

Defines the classes needed to implement the event queue using a priority queue that does not support searching. If used unwisely, the performance of the LineSweep algorithm would again fail to achieve its O((n+k) log n) as average case performance.

The problem with SlowEventQueue is that LineSweep requires no duplicate reporting of intersections. For this to work, you must be careful not to insert the same point multiple times into the event queue. This could happen if there are numerous pairs of lines that intersect at the same intersection point (an easy case to construct). Thus the insert method actually behaves more like merge.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.