Algorithm
Development Kit 1.0

Package algs.model.problems.segmentIntersection.linkedlist

Defines the classes needed to implement the LineSweep algorithm using double-linked lists to store the LineState.

See:
          Description

Class Summary
LineSweep Implementation using linkedList for lineState to show performance degradation as the size of the state increases.
LinkedListLineState Class that shows the performance degradation when the line state is stored using a linked list instead of an augmented, balanced binary tree.
 

Package algs.model.problems.segmentIntersection.linkedlist Description

Defines the classes needed to implement the LineSweep algorithm using double-linked lists to store the LineState.

Following such an approach prevents LineSweep from achieve its O((n+k) log n) behavior because of the costs in updating the line state. One will not see the performance degradation until the size of the line state exceeds a lower threshold. This example is provided as a warning. Make sure that when choosing to implement an algorithm that you choose the proper data structures that will achieve that goal. No detail can be overlooked. In this case, the costs of maintaining the line state will force LineSweep (using these linked lists) to be O(n^2) at times.


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.