zbMATH — the first resource for mathematics

Line-segment intersection made in-place. (English) Zbl 1131.68113
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 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.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68P10 Searching and sorting
68W05 Nonnumerical algorithms
Full Text: DOI
[1] Balaban, I.J., An optimal algorithm for finding segments [sic!] intersections, (), 211-219
[2] Bentley, J.L.; Ottmann, T.A., Algorithms for reporting and counting geometric intersections, IEEE transactions on computers, C-28, 9, 643-647, (1979) · Zbl 0414.68074
[3] Boissonnat, J.-D.; Snoeyink, J., Efficient algorithms for line and curve segment intersection using restricted predicates, Computational geometry: theory and applications, 16, 1, 35-52, (May 2000)
[4] Boissonnat, J.-D.; Vigneron, A., An elementary algorithm for reporting intersections of red/blue curve segments, Computational geometry: theory applications, 21, 3, 167-175, (March 2002)
[5] P. Bose, A. Maheshwari, P. Morin, J. Morrison, M. Smid, J. Vahrenhold, Space-efficient geometric divide-and-conquer algorithms, Computational Geometry: Theory & Applications (2006), doi:10.1016/j.comgeo.2006.03.006, in press, accepted November 2004. An extended abstract appeared in: Proceedings of the 20th European Workshop on Computational Geometry, 2004, pp. 65-68 · Zbl 1185.68772
[6] Brönnimann, H.; Chan, T.M.-Y.; Chen, E.Y., Towards in-place geometric algorithms, (), 239-246 · Zbl 1374.68646
[7] Brönnimann, H.; Iacono, J.; Katajainen, J.; Morin, P.; Morrison, J.; Toussaint, G.T., Space-efficient planar convex hull algorithms, Theoretical computer science, 321, 1, 25-40, (June 2004), An extended abstract appeared in the Proceedings of the Fifth Latin American Symposium on Theoretical Informatics, 2002, pp. 494-507
[8] B. Chazelle, Intersecting is easier than sorting, in: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 125-134
[9] Chazelle, B.; Edelsbrunner, H., An optimal algorithm for intersecting line segments in the plane, Journal of the ACM, 39, 1, 1-54, (January 1992)
[10] Chazelle, B.; Guibas, L.J., Fractional cascading: I. A data structuring technique, Algorithmica, 1, 2, 133-162, (1986) · Zbl 0639.68056
[11] E.Y. Chen, T.M.-Y. Chan, A space-efficient algorithm for line segment intersection, in: Proceedings of the 15th Canadian Conference on Computational Geometry, 2003, pp. 68-71
[12] Chen, J.-C., Optimizing stable in-place merging, Theoretical computer science, 302, 1-3, 191-210, (June 2003)
[13] Chen, J.-C., A simple algorithm for in-place merging, Information processing letters, 98, 1, 34-40, (April 2006)
[14] Floyd, R.W., Algorithm 245: treesort, Communications of the ACM, 7, 12, 701, (December 1964)
[15] Geffert, V.; Katajainen, J.; Pasanen, T., Asymptotically efficient in-place merging, Theoretical computer science, 237, 1-2, 159-181, (April 2000)
[16] ()
[17] Katajainen, J.; Pasanen, T., Stable minimum space partitioning in linear time, BIT: computer science, 32, 580-585, (1992) · Zbl 0756.68025
[18] Katajainen, J.; Pasanen, T., Sorting multisets stably in minimum space, Acta informatica, 31, 4, 301-313, (1994) · Zbl 0818.68066
[19] Kleinberg, J.; Tardos, É., Algorithm design, (2006), Addison-Wesley Boston, MA
[20] D.M. Mount, Geometric intersection, in: [16], Chapter 38, pp. 857-876
[21] Munro, J.I., An implicit data structure supporting insertion, deletion, and search in \(o(\log^2 n)\) time, Journal of computer and system sciences, 33, 1, 66-74, (August 1986)
[22] Pardo, L.T., Stable sorting and merging with optimal space and time bounds, SIAM journal on computing, 6, 2, 351-372, (June 1977)
[23] ()
[24] Salowe, J.S.; Steiger, W.L., Stable unmerging in linear time and constant space, Information processing letters, 25, 3, 285-294, (July 1987)
[25] S. Schirra, Robustness and precision issues in geometric computation, in: [23], Chapter 14, pp. 597-632 · Zbl 0947.68153
[26] Vahrenhold, J., Line-segment intersection made in-place, (), 146-157 · Zbl 1161.68820
[27] Williams, J.W.J., Algorithm 232: heapsort, Communications of the ACM, 7, 6, 347-348, (June 1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.