zbMATH — the first resource for mathematics

Space-efficient geometric divide-and-conquer algorithms. (English) Zbl 1185.68772
Summary: We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W05 Nonnumerical algorithms
Full Text: DOI
[1] Bentley, J.L.; Shamos, M.I., Divide-and-conquer in multidimensional space, (), 220-230
[2] Blum, M.; Floyd, R.W.; Pratt, V.R.; Rivest, R.L.; Tarjan, R.E., Time bounds for selection, Journal of computer and system sciences, 7, 4, 448-461, (August 1973)
[3] Brönnimann, H.; Chan, M.-Y., Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time, (), 162-171 · Zbl 1196.68296
[4] H. Brönnimann, T.M.-Y. Chan, E. Chen, Towards in-place geometric algorithms and data structures, in: Proceedings of the Twentieth ACM Symposium on Computational Geometry, 2004, pp. 239-246 · Zbl 1374.68646
[5] Brönnimann, H.; Iacono, J.; Katajainen, J.; Morin, P.; Morrison, J.; Toussaint, G.T., Optimal in-place planar convex hull algorithms, (), 494-507 · Zbl 1059.68626
[6] 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
[7] Clarkson, K.L.; Shor, P.W., Applications of random sampling in computational geometry II, Discrete computational geometry, 4, 387-421, (1989) · Zbl 0681.68060
[8] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to algorithms, (2001), McGraw-Hill
[9] Geffert, V.; Katajainen, J.; Pasanen, T., Asymptotically efficient in-place merging, Theoretical computer science, 237, 1-2, 159-181, (April 2000)
[10] M.T. Goodrich, J.-J. Tsay, D.E. Vengroff, J.S. Vitter, External-memory computational geometry, in: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 714-723
[11] Hoare, C.A.R., Algorithm 63 (PARTITION) and algorithm 65 (FIND), Communications of the ACM, 4, 7, 321-322, (1961)
[12] Katajainen, J.; Pasanen, T., Stable minimum space partitioning in linear time, Bit, 32, 580-585, (1992) · Zbl 0756.68025
[13] Katajainen, J.; Pasanen, T., Sorting multisets stably in minimum space, Acta informatica, 31, 4, 301-313, (1994) · Zbl 0818.68066
[14] Knuth, D.E., The art of computer programming: fundamental algorithms, vol. 1, (1997), Addison-Wesley · Zbl 0191.17903
[15] Preparata, F.P.; Shamos, M.I., Computational geometry. an introduction, (1988), Springer Berlin
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.