Mastering Algorithms With C - Kyle Loudon [225]
An alternative approach to Jarvis's march for computing convex hulls. Graham's scan works by maintaining a stack of candidate points for the convex hull. Each point is pushed onto the stack once. All points not in the convex hull are eventually popped off the stack so that when the algorithm terminates, the stack contains only the points in the convex hull. Graham's scan has a runtime complexity of O (n lg n), where n is the number of points in the set to enclose.
Index
A note on the digital index
A link in an index entry is displayed as the section title in which that entry appears. Because some sections have multiple index markers, it is not unusual for an entry to have several links to the same section. Clicking on any link will take you directly to the place in the text in which the marker appears.
Symbols
Θ-notation, Related Topics, Related Topics, Related Topics
A
abstract datatypes, An Introduction to Data Structures
abstract stack machines, Stacks and Queues, Binary Tree Example: Expression Processing
abstraction, An Introduction to Data Structures
activation records, Basic Recursion, Stacks and Queues
activations, Basic Recursion
adaptive Huffman coding, Related Topics
Adelson-Velskii and Landis (AVL) trees, Implementation and Analysis of Binary Search Trees
adjacency, Description of Graphs
adjacency-list representation of a graph, Description of Graphs
adjacency-matrix representation of a graph, Description of Graphs, Related Topics
AdjList structure, Implementation and Analysis of Graphs
aggregate data, Aggregates and Pointer Arithmetic
algorithms, An Introduction to Data Structures, An Introduction to Algorithms, An Introduction to Algorithms, An Introduction to Algorithms, An Introduction to Algorithms, General Approaches in Algorithm Design, Randomized algorithms, Divide-and-conquer algorithms, Dynamic-programming solutions, Greedy algorithms, Approximation algorithms, Analysis of Algorithms, O-Notation, Computational Complexity, Graph Algorithms, Geometric Algorithms
abstraction, An Introduction to Data Structures
analysis of, Analysis of Algorithms
classification of, General Approaches in Algorithm Design, Randomized algorithms, Divide-and-conquer algorithms, Dynamic-programming solutions, Greedy algorithms, Approximation algorithms
approximation, Approximation algorithms
divide-and-conquer, Divide-and-conquer algorithms
dynamic-programming solutions, Dynamic-programming solutions
greedy, Greedy algorithms
randomized, Randomized algorithms
defined, An Introduction to Algorithms
efficiency, O-Notation, Computational Complexity
geometric, Geometric Algorithms (see geometric algorithms)
graph, Graph Algorithms (see graph algorithms)
reasons for using, An Introduction to Algorithms
reusability, An Introduction to Algorithms
all-pairs shortest-paths problem, Related Topics
alloc_frame function, Linked List Example: Frame Management
ancestor nodes, Description of Binary Trees
approximating distances on Earth, Geometric Algorithms, Arc Length Example: Approximating Distances on Earth
approximating functions, Numerical Methods
approximation algorithms, Approximation algorithms
arc length, Description of Arc Length on Spherical Surfaces, Description of Arc Length on Spherical Surfaces, Rectilinear and Spherical Coordinates, Rectilinear and Spherical Coordinates, Converting Between Coordinate Systems, Computing the Length of an Arc, Interface for Arc Length on Spherical Surfaces, Description, Implementation and Analysis of Arc Length on Spherical Surfaces, Arc Length Example: Approximating Distances on Earth, Arc Length Example: Approximating Distances on Earth, Arc Length Example: Approximating Distances on Earth, Arc Length Example: Approximating Distances on Earth, Arc Length Example: Approximating Distances on Earth, Arc Length Example: Approximating Distances on Earth
approximating distances on Earth, Arc Length Example: Approximating Distances on Earth
coordinate conversion, Converting Between Coordinate Systems
description