List of Algorithms | Geometric Data Structures for Computer Graphics2006

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.

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.

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.

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.

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 ₁ = P ₁ to p ₂ = 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.)

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 ₁ + h ₂ + h _m ₊₁ = e + b.
Algorithm 9.4: ExpansionSum computes a non-overlapping expansion h ₁ + + 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 ₁ + + h ₂ _m = be.
Algorithm 9.8: Compress computes a non-overlapping expansion h ₁ + + 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.

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.
Algorithm 10.7: The extended INSERT operation.