Output-sensitive algorithm
Encyclopedia
In computer science
, an output-sensitive 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, output-sensitive 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.
Output-sensitive algorithms arise frequently in computational geometry
applications and have been described for problems such as hidden surface removal and resolving range filter conflicts in router tables.
Frank Nielsen describes a general paradigm of output-sensitive algorithms known as grouping and querying and gives such an algorithm for computing cells of a Voronoi diagram
. 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, an output-sensitive algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Convex hull algorithms
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science, see "Convex hull applications"....
for finding the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of a finite set of points in the plane require Ω
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) time for n points; even relatively simple algorithms like the Graham scan
Graham scan
The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O. It is named after Ronald Graham, who published the original algorithm in 1972...
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, output-sensitive algorithms such as the ultimate convex hull algorithm and Chan's algorithm
Chan's algorithm
In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2 or 3 dimensional space. The algorithm takes O time, where h is the number of vertices of the output...
which require only O(n log h) time are considerably faster for such point sets.
Output-sensitive algorithms arise frequently in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
applications and have been described for problems such as hidden surface removal and resolving range filter conflicts in router tables.
Frank Nielsen describes a general paradigm of output-sensitive algorithms known as grouping and querying and gives such an algorithm for computing cells of a Voronoi diagram
Voronoi diagram
In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
. 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.