About this document
Efficient Stabbing Line Algorithm by sanjib is a document available to read on EtoBox.
The document presents an algorithm for determining a line (called a stabbing line) that intersects each of n given line segments in a plane. The algorithm computes a description of all stabbing lines in O(n log n) time, which is optimal. This description, called the stabbing region, requires O(n) space and can be used to determine if a specified line is a stabbing line in O(log n) time. The problem of maintaining the description while inserting or deleting line segments is also addressed.
- Author
- sanjib
- Language
- EN