| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 414438 | Computational Geometry | 2007 | 18 Pages |
Abstract
We present a space-efficient algorithm for reporting all k intersections induced by a set of n line segments in the plane. Our algorithm is an in-place variant of Balaban's algorithm and, in the worst case, runs in O(nlog2n+k) time using O(1) extra words of memory in addition to the space used for the input to the algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
