×

zbMATH — the first resource for mathematics

In-place algorithms for computing (Layers of) maxima. (English) Zbl 1184.68558
Summary: We describe space-efficient algorithms for solving problems related to finding maxima among points in two and three dimensions. Our algorithms run in optimal \(\mathcal{O}(n\log n)\) time and occupy only constant extra space in addition to the space needed for representing the input.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Software:
heapsort
PDF BibTeX Cite
Full Text: DOI
References:
[1] Brönnimann, H., Chan, T.M.-Y.: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom. Theory Appl. 34(2), 75–82 (2006) · Zbl 1089.65014
[2] Brönnimann, H., Chan, T.M.-Y., Chen, E.Y.: Towards in-place geometric algorithms. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 239–246. ACM Press, New York (2004) · Zbl 1374.68646
[3] Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23(4), 214–229 (1980) · Zbl 0434.68049
[4] Bentley, J.L., Clarkson, K.L., Levine, D.B.: Fast linear expected-time algorithms for computing maxima and convex hulls. Algorithmica 9(2), 168–183 (1993) · Zbl 0766.68132
[5] Buchsbaum, A.L., Goodrich, M.T.: Three-dimensional layers of maxima. Algorithmica 39(4), 275–286 (2004) · Zbl 1090.68114
[6] Brönnimann, H., Iacono, J., Katajainen, J., Morin, P., Morrison, J., Toussaint, G.T.: Space-efficient planar convex hull algorithms. Theor. Comput. Sci. 321(1), 25–40 (2004) · Zbl 1068.68153
[7] Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, pp. 421–430. IEEE Computer Society, Los Alamitos (2001)
[8] Bose, P., Maheshwari, A., Morin, P., Morrison, J., Smid, M., Vahrenhold, J.: Space-efficient geometric divide-and-conquer algorithms. Comput. Geom. Theory Appl. 37(3), 209–227 (2007) · Zbl 1185.68772
[9] Chen, E.Y., Chan, T.M.-Y.: A space-efficient algorithm for line segment intersection. In Proceedings of the 15th Canadian Conference on Computational Geometry, pp. 68–71, 2003
[10] Chazelle, B.M.: On the convex layers of a planar set. IEEE Trans. Inf. Theory IT-31(4), 509–517 (1985) · Zbl 0573.68035
[11] Chan, T.M.Y.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Comput. Geom. Theory Appl. 16(14), 361–368 (1996) · Zbl 0857.68111
[12] Chen, J.-C.: Optimizing stable in-place merging. Theor. Comput. Sci. 302(1–3), 191–210 (2003) · Zbl 1051.68050
[13] Chen, J.-C.: A simple algorithm for in-place merging. Inf. Process. Lett. 98(1), 34–40 (2006) · Zbl 1186.68541
[14] Dai, H.K., Zhang, X.W.: Improved linear expected-time algorithms for computing maxima. In: Farach-Colton, M. (ed.) Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004). Lecture Notes in Computer Science, vol. 2976, pp. 181–192. Springer, Berlin (2004) · Zbl 1196.68298
[15] Geffert, V., Katajainen, J., Pasanen, T.: Asymptotically efficient in-place merging. Theor. Comput. Sci. 237(1–2), 159–181 (2000) · Zbl 0939.68160
[16] Kapoor, S.: Dynamic maintenance of maxima of 2-D point sets. SIAM J. Comput. 29(6), 1858–1877 (2000) · Zbl 0953.68062
[17] Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469–476 (1975) · Zbl 0316.68030
[18] Katajainen, J., Pasanen, T.: Stable minimum space partitioning in linear time. BIT: Comput. Sci. 32, 580–585 (1992) · Zbl 0756.68025
[19] Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: An online algorithm for skyline queries. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 275–286. Morgan Kaufmann, San Mateo (2002)
[20] Matoušek, J.: Computing dominances in E n . Inf. Process. Lett. 38(5), 277–278 (1991) · Zbl 0738.68080
[21] Munro, J.I.: An implicit data structure supporting insertion, deletion, and search in o(log 2 n) time. J. Comput. Syst. Sci. 33(1), 66–74 (1986) · Zbl 0625.68044
[22] Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23(2), 166–204 (1981) · Zbl 0474.68082
[23] Preparata, F.P., Shamos, M.I.: Computational Geometry. An Introduction, 2nd edn. Springer, Berlin (1988) · Zbl 0575.68059
[24] Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30(1), 41–82 (2005) · Zbl 05457059
[25] Salowe, J.S., Steiger, W.L.: Stable unmerging in linear time and constant space. Inf. Process. Lett. 25(3), 285–294 (1987) · Zbl 0653.68053
[26] Tan, K.-L., Eng, P.-K., Ooi, B.C.: Efficient progressive skyline computation. In: Apers, P.M.G., Atzeni, P., Ceri, S., Paraboschi, S., Ramamohanarao, K., Snodgrass, R.T. (eds.) Proceedings of the 27th International Conference on Very Large Data Bases, pp. 301–310. Morgan Kaufmann, San Mateo (2001)
[27] Vahrenhold, J.: Line-segment intersection made in-place. Comput. Geom. Theory Appl. 38(3), 213–230 (2007) · Zbl 1131.68113
[28] Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM 7(6), 347–348 (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.