
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.
O(1) space complexity, computational complexity, Control and Optimization, in-place algorithms, Space-efficient algorithms, Computer Science Applications, Line-segment intersection, Computational Mathematics, Computational Theory and Mathematics, Numerical aspects of computer graphics, image analysis, and computational geometry, In-place algorithms, Computer graphics; computational geometry (digital and algorithmic aspects), line-segment intersection, Geometry and Topology, space-efficient algorithms, Searching and sorting, Nonnumerical algorithms
O(1) space complexity, computational complexity, Control and Optimization, in-place algorithms, Space-efficient algorithms, Computer Science Applications, Line-segment intersection, Computational Mathematics, Computational Theory and Mathematics, Numerical aspects of computer graphics, image analysis, and computational geometry, In-place algorithms, Computer graphics; computational geometry (digital and algorithmic aspects), line-segment intersection, Geometry and Topology, space-efficient algorithms, Searching and sorting, Nonnumerical algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
