×

zbMATH — the first resource for mathematics

Faster output-sensitive skyline computation algorithm. (English) Zbl 1371.68294
Summary: We present the second output-sensitive skyline computation algorithm which is faster than the only existing output-sensitive skyline computation algorithm [D. G. Kirkpatrick and R. Seidel, “Output-size sensitive algorithms for finding maximal vectors”, in: Proceedings of the 1st annual symposium on computational geometry, SCG’85. New York, NY: Association for Computing Machinery (ACM). 89–96 (1985; doi:10.1145/323233.323246)] in worst case because our algorithm does not rely on the existence of a linear time procedure for finding medians.
MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kirkpatrick, D. G.; Seidel, R., Output-size sensitive algorithms for finding maximal vectors, (Symposium on Computational Geometry, (1985)), 89-96
[2] Bentley, J. L., Multidimensional divide-and-conquer, Commun. ACM, 23, 4, 214-229, (1980) · Zbl 0434.68049
[3] Bentley, J. L.; Clarkson, K. L.; Levine, D. B., Fast linear expected-time algorithms for computing maxima and convex hulls, (SODA, (1990)), 179-187 · Zbl 0800.68959
[4] Bentley, J. L.; Kung, H. T.; Schkolnick, M.; Thompson, C. D., On the average number of maxima in a set of vectors and applications, J. ACM, 25, 4, 536-543, (1978) · Zbl 0388.68056
[5] 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
[6] Hu, X.; Sheng, C.; Tao, Y.; Yang, Y.; Zhou, S., Output-sensitive skyline algorithms in external memory, (SODA, (2013)), 887-900 · Zbl 1423.68545
[7] Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E., Time bounds for selection, J. Comput. Syst. Sci., 7, 4, 448-461, (1973) · Zbl 0278.68033
[8] Chan, T. M.; Lee, P., On constant factors in comparison-based geometric algorithms and data structures, (Symposium on Computational Geometry, (2014)), 40 · Zbl 1395.68295
[9] Luccio, F.; Preparata, F., On finding the maxima of a set of vectors, (1973), Instituto di Scienze dell’Informazione, Universit√† di Pisa, 56100 Corso Italia 40
[10] Chan, T. M., Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete Comput. Geom., 16, 4, 361-368, (1996) · Zbl 0857.68111
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.