 Outputsensitive algorithm

In computer science, an outputsensitive algorithm is an algorithm whose running time depends not only on the size of the input but also on the size of the output. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.
For example, convex hull algorithms for finding the convex hull of a finite set of points in the plane require Ω(n log n) time for n points; even relatively simple algorithms like the Graham scan achieve this lower bound. If the convex hull uses all n points, this is the best we can do; however, for many practical sets of points, and in particular for random sets of points, the number of points h in the convex hull is typically much smaller than n. Consequently, outputsensitive algorithms such as the ultimate convex hull algorithm and Chan's algorithm which require only O(n log h) time are considerably faster for such point sets.
Outputsensitive algorithms arise frequently in computational geometry applications and have been described for problems such as hidden surface removal^{[1]} and resolving range filter conflicts in router tables^{[2]}.
Frank Nielsen describes a general paradigm of outputsensitive algorithms known as grouping and querying and gives such an algorithm for computing cells of a Voronoi diagram.^{[3]} Nielsen breaks these algorithms into two stages: estimating the output size, and then building data structures based on that estimate which are queried to construct the final solution.
See also
References
 ^ Micha Sharir, Mark Overmars. A simple outputsensitive algorithm for hidden surface removal. ACM Transactions on Graphics. Vol. 11, issue 1, pp.1–11. January 1992. ISSN 07300301. ACM portal (login required)
 ^ Khaireel A. Mohamed and Christine Kupich. An O(n log n) OutputSensitive Algorithm to Detect and Resolve Conflicts for 1D Range Filters in Router Tables. Institut für Informatik. August 5, 2006. ftp://ftp.informatik.unifreiburg.de/documents/reports/report226/report00226.ps.gz
 ^ Frank Nielsen. Grouping and Querying: A Paradigm to Get OutputSensitive Algorithms. Revised Papers from the Japanese Conference on Discrete and Computational Geometry, pp.250–257. 1998. ISBN:3540671811. http://www.sonycsl.co.jp/person/nielsen/PT/groupingquerying/ngrouping.ps
Categories:
Wikimedia Foundation. 2010.