Output-sensitive algorithm

Output-sensitive algorithm

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[1] and resolving range filter conflicts in router tables[2].

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.[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

  1. ^ Micha Sharir, Mark Overmars. A simple output-sensitive algorithm for hidden surface removal. ACM Transactions on Graphics. Vol. 11, issue 1, pp.1–11. January 1992. ISSN 0730-0301. ACM portal (login required)
  2. ^ Khaireel A. Mohamed and Christine Kupich. An O(n log n) Output-Sensitive Algorithm to Detect and Resolve Conflicts for 1D Range Filters in Router Tables. Institut für Informatik. August 5, 2006. ftp://ftp.informatik.uni-freiburg.de/documents/reports/report226/report00226.ps.gz
  3. ^ Frank Nielsen. Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms. Revised Papers from the Japanese Conference on Discrete and Computational Geometry, pp.250–257. 1998. ISBN:3-540-67181-1. http://www.sonycsl.co.jp/person/nielsen/PT/groupingquerying/n-grouping.ps

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Kirkpatrick–Seidel algorithm — The Kirkpatrick–Seidel algorithm, called by its authors the ultimate planar convex hull algorithm is an algorithm for computing the convex hull of a set of points in the plane, with O( n log h ) time complexity, where n is the number of input… …   Wikipedia

  • 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(n log h) time, where h is the …   Wikipedia

  • k-nearest neighbor algorithm — KNN redirects here. For other uses, see KNN (disambiguation). In pattern recognition, the k nearest neighbor algorithm (k NN) is a method for classifying objects based on closest training examples in the feature space. k NN is a type of instance… …   Wikipedia

  • Nagle's algorithm — Nagle s algorithm, named after John Nagle, is a means of improving the efficiency of TCP/IP networks by reducing the number of packets that need to be sent over the network. Nagle s document, Congestion Control in IP/TCP Internetworks (RFC 896)… …   Wikipedia

  • Deterministic algorithm — In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence… …   Wikipedia

  • CURE data clustering algorithm — CURE (Clustering Using REpresentatives) is an efficient data clustering algorithm for large databases that is more robust to outliers and identifies clusters having non spherical shapes and wide variances in size. Contents 1 Drawbacks of… …   Wikipedia

  • 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 . In computational geometry, numerous algorithms are proposed for computing the convex… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Interval tree — In computer science, an interval tree, also called a segment tree or segtree, is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is… …   Wikipedia

  • Circle graph — For the chart, see Pie chart. A circle with five chords and the corresponding circle graph. In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”