Line-segment intersection made in-place (Q2385700): Difference between revisions

An in-place algorithm is an algorithm which transforms a data structure using a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. The paper deals with the problem of designing space-efficient algorithms for solving merging, sorting and partitioning problems. The author presents an in-place version of the optimal algorithm proposed by \textit{Balaban} [Proceedings of the 11th Annual Symposium on Computational Geometry, ACM Press, New York, 211--219 (1995)]. The main result is the following theorem: All \(k\) intersections induced by a set of \(n\) segments in the plane can be computed in \(O(n\log^2(n)+k)\) time using \(O(1)\) very little extra words of memory. The technique is to identify building blocks of the original algorithm and to try to replace them by in-place counterparts wherever possible. An appendix is devoted to degenerate configurations.