Chapter 2: Orthogonal Windowing and Stabbing Queries
Algorithm 2.1: Computing an interval tree for a set of intervals, recursively.
Algorithm 2.2: Answering a stabbing query for an interval tree v and a value x q , recursively.
Algorithm 2.3: Construction of a simple balanced one-dimensional search tree.
Algorithm 2.4: Building a segment tree.
Algorithm 2.5: Insertion of a segment s in the segment tree.
Algorithm 2.6: The stabbing query for a segment tree.
Algorithm 2.7: The inductive construction algorithm of a multi-level segment tree.
Algorithm 2.8: The inductive query operation for a multi-level segment tree.
Algorithm 2.9: Recursive construction of a kd-tree .
Algorithm 2.10: The query procedure of the d-dimensional kd-tree.
Algorithm 2.11: The inductive construction algorithm of a d-dimensional range tree.
Algorithm 2.12: The inductive query operation for a d-dimensional range tree.
Chapter 3: BSP Trees
Algorithm 3.1: The first building block of the algorithm for Boolean operations is the procedure that splits a BSP.
Algorithm 3.2: The second building block for Boolean operations merges two BSPs.
Algorithm 3.3: Testing for ray-scene intersections with a deferred BSP.
Chapter 4: Bounding Volume Hierarchies
Algorithm 4.1: Construction of BVHs by insertion.
Algorithm 4.2: General scheme of hierarchical collision detection.
Algorithm 4.3: Time-critical traversal scheme. The recursive procedure is now replaced by a queue.
Chapter 6: Voronoi Diagrams
Algorithm 6.1: The incremental construction of the Voronoi diagram.
Algorithm 6.2: Inserting a new site in a Delaunay triangulation.
Algorithm 6.3: Searching for the triangle in the Delaunay diagram that contains p.
Algorithm 6.4: The DAG and its DCEL are updated by flip operations, cross-references between triangles in DAG and T(DAG) are created by FlipDCEL.
Algorithm 6.5: Update of the DAG and its DCEL by inserting p into triangle t.
Algorithm 6.6: The construction of a slab search structure for the region query returns a 2D arrayS. For each vertical line, the array contains a sorted array of crossing segments.
Algorithm 6.7: The region query can be answered efficiently using a slab decomposition and a binary search.
Algorithm 6.8: Answering a region query by tracing a line through the DCEL.
Algorithm 6.9: Lloyds algorithm to compute a centroidal Voronoi diagram for a region R.
Algorithm 6.10: Algorithm to generate a mosaic.
Algorithm 6.11: Simple Monte Carlolike method to compute natural neighbors.
Chapter 7: Geometric Proximity Graphs
Algorithm 7.1: Simple algorithm to construct the GG, starting from the Delaunay graph of a set of points.
Algorithm 7.2: Simple algorithm and heuristic to build the GG.
Algorithm 7.3: Simple algorithm to compute the r-SIG in O(n) time on average.
Algorithm 7.4: Simple algorithm to clean (edit) a training set from incorrectly labeled samples.
Algorithm 7.5: Pseudocode for the root-finding algorithm based on interpolation search. P is an array containing the points of the shortest path from p 1 = P 1 to p 2 = P n , which can be precomputed. d i = f B (P i ) approximates the distance of P i to object B. (*) Note that either d l or d r is negative.
Algorithm 7.6: This algorithm can be used to initialize P for Algorithm 7.5 if precomputing and storing all shortest paths in a map is too expensive. (q is a priority queue.)
Chapter 8: Kinetic Data Structures
Algorithm 8.1: Basic main loop of most kinetic data structures.
Algorithm 8.2: Simple algorithm for answering a stabbing query.
Algorithm 8.3: Updating a kinetic segment tree.
Chapter 9: Degeneracy and Robustness
Algorithm 9.1: FastTwoSum easily computes a non-overlapping expansion.
Algorithm 9.2: TwoSum computes a non-overlapping expansion x + y = a + b.
Algorithm 9.3: GrowExpansion computes a non-overlapping expansion h 1 + h 2 + h m +1 = e + b.
Algorithm 9.4: ExpansionSum computes a non-overlapping expansion h 1 + + h m + n = e + f.
Algorithm 9.5: TwoProduct computes a non-overlapping expansion x + y = a — b.
Algorithm 9.6: Split splits a floating-point value a into a = x + y,where x has (p ˆ s) bits and y has (s ˆ 1) bits.
Algorithm 9.7: ScaleExpansion computes a non-overlapping expansion h 1 + + h 2 m = be.
Algorithm 9.8: Compress computes a non-overlapping expansion h 1 + + h n = e with non-zero entries. The largest component is a good approximation of e.
Algorithm 9.9: The ordering predicate for a simple perturbation scheme.
Algorithm 9.10: An -arithmetic test for T(a, b, c) and T(a, c, b).
Algorithm 9.11: Computing the upper-left hull of an y-monotone chain.
Chapter 10: Dynamization of Geometric Data Structures
Algorithm 10.1: Computing the binary decomposition of a set of objects D.
Algorithm 10.2: Collecting all elements of W.
Algorithm 10.3: Computing the query for the binary decomposition W.
Algorithm 10.4: Destroying the structure W.
Algorithm 10.5: Inserting an element into the binary decomposition.
Algorithm 10.6: The extended DELETE operation incorporates the half- size rule and the WeakDelete operation.