ALGORITHMS OF INFORMATICS
   Next

ALGORITHMS OF INFORMATICS

Volume 2

Új Széchenyi Terv logó.

Table of Contents

IV. COMPUTER NETWORKS
13. Distributed Algorithms
13.1. 13.1 Message passing systems and algorithms
13.1.1. 13.1.1 Modeling message passing systems
13.1.2. 13.1.2 Asynchronous systems
13.1.3. 13.1.3 Synchronous systems
13.2. 13.2 Basic algorithms
13.2.1. 13.2.1 Broadcast
13.2.2. 13.2.2 Construction of a spanning tree
13.3. 13.3 Ring algorithms
13.3.1. 13.3.1 The leader election problem
13.3.2. 13.3.2 The leader election algorithm
13.3.3. 13.3.3 Analysis of the leader election algorithm
13.4. 13.4 Fault-tolerant consensus
13.4.1. 13.4.1 The consensus problem
13.4.2. 13.4.2 Consensus with crash failures
13.4.3. 13.4.3 Consensus with Byzantine failures
13.4.4. 13.4.4 Lower bound on the ratio of faulty processors
13.4.5. 13.4.5 A polynomial algorithm
13.4.6. 13.4.6 Impossibility in asynchronous systems
13.5. 13.5 Logical time, causality, and consistent state
13.5.1. 13.5.1 Logical time
13.5.2. 13.5.2 Causality
13.5.3. 13.5.3 Consistent state
13.6. 13.6 Communication services
13.6.1. 13.6.1 Properties of broadcast services
13.6.2. 13.6.2 Ordered broadcast services
13.6.3. 13.6.3 Multicast services
13.7. 13.7 Rumor collection algorithms
13.7.1. 13.7.1 Rumor collection problem and requirements
13.7.2. 13.7.2 Efficient gossip algorithms
13.8. 13.8 Mutual exclusion in shared memory
13.8.1. 13.8.1 Shared memory systems
13.8.2. 13.8.2 The mutual exclusion problem
13.8.3. 13.8.3 Mutual exclusion using powerful primitives
13.8.4. 13.8.4 Mutual exclusion using read/write registers
13.8.5. 13.8.5 Lamport's fast mutual exclusion algorithm
14. Network Simulation
14.1. 14.1 Types of simulation
14.2. 14.2 The need for communications network modelling and simulation
14.3. 14.3 Types of communications networks, modelling constructs
14.4. 14.4 Performance targets for simulation purposes
14.5. 14.5 Traffic characterisation
14.6. 14.6 Simulation modelling systems
14.6.1. 14.6.1 Data collection tools and network analysers
14.6.2. 14.6.2 Model specification
14.6.3. 14.6.3 Data collection and simulation
14.6.4. 14.6.4 Analysis
14.6.5. 14.6.5 Network Analysers
14.6.6. 14.6.6 Sniffer
14.7. 14.7 Model Development Life Cycle (MDLC)
14.8. 14.8 Modelling of traffic burstiness
14.8.1. 14.8.1 Model parameters
14.8.2. 14.8.2 Implementation of the Hurst parameter
14.8.3. 14.8.3 Validation of the baseline model
14.8.4. 14.8.4 Consequences of traffic burstiness
14.8.5. 14.8.5 Conclusion
14.9. 14.9 Appendix A
14.9.1. 14.9.1 Measurements for link utilisation
14.9.2. 14.9.2 Measurements for message delays
15. Parallel Computations
15.1. 15.1 Parallel architectures
15.1.1. 15.1.1 SIMD architectures
15.1.2. 15.1.2 Symmetric multiprocessors
15.1.3. 15.1.3 Cache-coherent NUMA architectures
15.1.4. 15.1.4 Non-cache-coherent NUMA architectures
15.1.5. 15.1.5 No remote memory access architectures
15.1.6. 15.1.6 Clusters
15.1.7. 15.1.7 Grids
15.2. 15.2 Performance in practice
15.3. 15.3 Parallel programming
15.3.1. 15.3.1 MPI programming
15.3.2. 15.3.2 OpenMP programming
15.3.3. 15.3.3 Other programming models
15.4. 15.4 Computational models
15.4.1. 15.4.1 PRAM
15.4.2. 15.4.2 BSP, LogP and QSM
15.4.3. 15.4.3 Mesh, hypercube and butterfly
15.5. 15.5 Performance in theory
15.6. 15.6 PRAM algorithms
15.6.1. 15.6.1 Prefix
15.6.2. 15.6.2 Ranking
15.6.3. 15.6.3 Merge
15.6.4. 15.6.4 Selection
15.6.5. 15.6.5 Sorting
15.7. 15.7 Mesh algorithms
15.7.1. 15.7.1 Prefix on chain
15.7.2. 15.7.2 Prefix on square
16. Systolic Systems
16.1. 16.1 Basic concepts of systolic systems
16.1.1. 16.1.1 An introductory example: matrix product
16.1.2. 16.1.2 Problem parameters and array parameters
16.1.3. 16.1.3 Space coordinates
16.1.4. 16.1.4 Serialising generic operators
16.1.5. 16.1.5 Assignment-free notation
16.1.6. 16.1.6 Elementary operations
16.1.7. 16.1.7 Discrete timesteps
16.1.8. 16.1.8 External and internal communication
16.1.9. 16.1.9 Pipelining
16.2. 16.2 Space-time transformation and systolic arrays
16.2.1. 16.2.1 Further example: matrix product
16.2.2. 16.2.2 The space-time transformation as a global view
16.2.3. 16.2.3 Parametric space coordinates
16.2.4. 16.2.4 Symbolically deriving the running time
16.2.5. 16.2.5 How to unravel the communication topology
16.2.6. 16.2.6 Inferring the structure of the cells
16.3. 16.3 Input/output schemes
16.3.1. 16.3.1 From data structure indices to iteration vectors
16.3.2. 16.3.2 Snapshots of data structures
16.3.3. 16.3.3 Superposition of input/output schemes
16.3.4. 16.3.4 Data rates induced by space-time transformations
16.3.5. 16.3.5 Input/output expansion
16.3.6. 16.3.6 Coping with stationary variables
16.3.7. 16.3.7 Interleaving of calculations
16.4. 16.4 Control
16.4.1. 16.4.1 Cells without control
16.4.2. 16.4.2 Global control
16.4.3. 16.4.3 Local control
16.4.4. 16.4.4 Distributed control
16.4.5. 16.4.5 The cell program as a local view
16.5. 16.5 Linear systolic arrays
16.5.1. 16.5.1 Matrix-vector product
16.5.2. 16.5.2 Sorting algorithms
16.5.3. 16.5.3 Lower triangular linear equation systems
V. DATA BASES
17. Memory Management
17.1. 17.1 Partitioning
17.1.1. 17.1.1 Fixed partitions
17.1.2. 17.1.2 Dynamic partitions
17.2. 17.2 Page replacement algorithms
17.2.1. 17.2.1 Static page replacement
17.2.2. 17.2.2 Dynamic paging
17.3. 17.3 Anomalies
17.3.1. 17.3.1 Page replacement
17.3.2. 17.3.2 Scheduling with lists
17.3.3. 17.3.3 Parallel processing with interleaved memory
17.3.4. 17.3.4 Avoiding the anomaly
17.4. 17.4 Optimal file packing
17.4.1. 17.4.1 Approximation algorithms
17.4.2. 17.4.2 Optimal algorithms
17.4.3. 17.4.3 Shortening of lists (SL)
17.4.4. 17.4.4 Upper and lower estimations (ULE)
17.4.5. 17.4.5 Pairwise comparison of the algorithms
17.4.6. 17.4.6 The error of approximate algorithms
18. Relational Database Design
18.1. 18.1 Functional dependencies
18.1.1. 18.1.1 Armstrong-axioms
18.1.2. 18.1.2 Closures
18.1.3. 18.1.3 Minimal cover
18.1.4. 18.1.4 Keys
18.2. 18.2 Decomposition of relational schemata
18.2.1. 18.2.1 Lossless join
18.2.2. 18.2.2 Checking the lossless join property
18.2.3. 18.2.3 Dependency preserving decompositions
18.2.4. 18.2.4 Normal forms
18.2.5. 18.2.5 Multivalued dependencies
18.3. 18.3 Generalised dependencies
18.3.1. 18.3.1 Join dependencies
18.3.2. 18.3.2 Branching dependencies
19. Query Rewriting in Relational Databases
19.1. 19.1 Queries
19.1.1. 19.1.1 Conjunctive queries
19.1.2. 19.1.2 Extensions
19.1.3. 19.1.3 Complexity of query containment
19.2. 19.2 Views
19.2.1. 19.2.1 View as a result of a query
19.3. 19.3 Query rewriting
19.3.1. 19.3.1 Motivation
19.3.2. 19.3.2 Complexity problems of query rewriting
19.3.3. 19.3.3 Practical algorithms
20. Semi-structured Databases
20.1. 20.1 Semi-structured data and XML
20.2. 20.2 Schemas and simulations
20.3. 20.3 Queries and indexes
20.4. 20.4 Stable partitions and the PT-algorithm
20.5. 20.5 A()-indexes
20.6. 20.6 D()- and M()-indexes
20.7. 20.7 Branching queries
20.8. 20.8 Index refresh
VI. APPLICATIONS
21. Bioinformatics
21.1. 21.1 Algorithms on sequences
21.1.1. 21.1.1 Distances of two sequences using linear gap penalty
21.1.2. 21.1.2 Dynamic programming with arbitrary gap function
21.1.3. 21.1.3 Gotoh algorithm for affine gap penalty
21.1.4. 21.1.4 Concave gap penalty
21.1.5. 21.1.5 Similarity of two sequences, the Smith-Waterman algorithm
21.1.6. 21.1.6 Multiple sequence alignment
21.1.7. 21.1.7 Memory-reduction with the Hirschberg algorithm
21.1.8. 21.1.8 Memory-reduction with corner-cutting
21.2. 21.2 Algorithms on trees
21.2.1. 21.2.1 The small parsimony problem
21.2.2. 21.2.2 The Felsenstein algorithm
21.3. 21.3 Algorithms on stochastic grammars
21.3.1. 21.3.1 Hidden Markov Models
21.3.2. 21.3.2 Stochastic context-free grammars
21.4. 21.4 Comparing structures
21.4.1. 21.4.1 Aligning labelled, rooted trees
21.4.2. 21.4.2 Co-emission probability of two HMMs
21.5. 21.5 Distance based algorithms for constructing evolutionary trees
21.5.1. 21.5.1 Clustering algorithms
21.5.2. 21.5.2 Neighbour joining
21.6. 21.6 Miscellaneous topics
21.6.1. 21.6.1 Genome rearrangement
21.6.2. 21.6.2 Shotgun sequencing
22. Computer Graphics
22.1. 22.1 Fundamentals of analytic geometry
22.1.1. 22.1.1 Cartesian coordinate system
22.2. 22.2 Description of point sets with equations
22.2.1. 22.2.1 Solids
22.2.2. 22.2.2 Surfaces
22.2.3. 22.2.3 Curves
22.2.4. 22.2.4 Normal vectors
22.2.5. 22.2.5 Curve modelling
22.2.6. 22.2.6 Surface modelling
22.2.7. 22.2.7 Solid modelling with blobs
22.2.8. 22.2.8 Constructive solid geometry
22.3. 22.3 Geometry processing and tessellation algorithms
22.3.1. 22.3.1 Polygon and polyhedron
22.3.2. 22.3.2 Vectorization of parametric curves
22.3.3. 22.3.3 Tessellation of simple polygons
22.3.4. 22.3.4 Tessellation of parametric surfaces
22.3.5. 22.3.5 Subdivision curves and meshes
22.3.6. 22.3.6 Tessellation of implicit surfaces
22.4. 22.4 Containment algorithms
22.4.1. 22.4.1 Point containment test
22.4.2. 22.4.2 Polyhedron-polyhedron collision detection
22.4.3. 22.4.3 Clipping algorithms
22.5. 22.5 Translation, distortion, geometric transformations
22.5.1. 22.5.1 Projective geometry and homogeneous coordinates
22.5.2. 22.5.2 Homogeneous linear transformations
22.6. 22.6 Rendering with ray tracing
22.6.1. 22.6.1 Ray surface intersection calculation
22.6.2. 22.6.2 Speeding up the intersection calculation
22.7. 22.7 Incremental rendering
22.7.1. 22.7.1 Camera transformation
22.7.2. 22.7.2 Normalizing transformation
22.7.3. 22.7.3 Perspective transformation
22.7.4. 22.7.4 Clipping in homogeneous coordinates
22.7.5. 22.7.5 Viewport transformation
22.7.6. 22.7.6 Rasterization algorithms
22.7.7. 22.7.7 Incremental visibility algorithms
23. Human-Computer Interaction
23.1. 23.1 Multiple-choice systems
23.1.1. 23.1.1 Examples of multiple-choice systems
23.2. 23.2 Generating multiple candidate solutions
23.2.1. 23.2.1 Generating candidate solutions with heuristics
23.2.2. 23.2.2 Penalty method with exact algorithms
23.2.3. 23.2.3 The linear programming—penalty method
23.2.4. 23.2.4 Penalty method with heuristics
23.3. 23.3 More algorithms for interactive problem solving
23.3.1. 23.3.1 Anytime algorithms
23.3.2. 23.3.2 Interactive evolution and generative design
23.3.3. 23.3.3 Successive fixing
23.3.4. 23.3.4 Interactive multicriteria decision making
23.3.5. 23.3.5 Miscellaneous
Bibliography

List of Figures

14.1. Estimation of the parameters of the most common distributions.
14.2. An example normal distribution.
14.3. An example Poisson distribution.
14.4. An example exponential distribution.
14.5. An example uniform distribution.
14.6. An example Pareto distribution.
14.7. Exponential distribution of interarrival time with 10 sec on the average.
14.8. Probability density function of the Exp (10.0) interarrival time.
14.9. Visualisation of anomalies in packet lengths.
14.10. Large deviations between delta times.
14.11. Histogram of frame lengths.
14.12. The three modelling abstraction levels specified by the Project, Node, and Process editors.
14.13. Example for graphical representation of scalar data (upper graph) and vector data (lower graph).
14.14. Figure 14.14 shows four graphs represented by the Analysis Tool.
14.15. Data Exchange Chart.
14.16. Summary of Delays.
14.17. Diagnosis window.
14.18. Statistics window.
14.19. Impact of adding more bandwidth on the response time.
14.20. Baseline model for further simulation studies.
14.21. Comparison of RMON Standards.
14.22. The self-similar nature of Internet network traffic.
14.23. Traffic traces.
14.24. Measured network parameters.
14.25. Part of the real network topology where the measurements were taken.
14.26. “Message Source” remote client.
14.27. Interarrival time and length of messages sent by the remote client.
14.28. The Pareto probability distribution for mean 440 bytes and Hurst parameter The Pareto probability distribution for mean 440 bytes and Hurst parameter H=0.55 ..
14.29. The internal links of the 6Mbps ATM network with variable rate control (VBR).
14.30. Parameters of the 6Mbps ATM connection.
14.31. The “Destination” subnetwork.
14.32. utilisation of the frame relay link in the baseline model.
14.33. Baseline message delay between the remote client and the server.
14.34. Input buffer level of remote router.
14.35. Baseline utilisations of the DS-3 link and Ethernet link in the destination.
14.36. Network topology of bursty traffic sources with various Hurst parameters.
14.37. Simulated average and peak link utilisation.
14.38. Response time and burstiness.
14.39. Relation between the number of cells dropped and burstiness.
14.40. Utilisation of the frame relay link for fixed size messages.
14.41. Utilisation of the frame relay link for Hurst parameter Utilisation of the frame relay link for Hurst parameter H=0.55 ..
14.42. Utilisation of the frame relay link for Hurst parameter Utilisation of the frame relay link for Hurst parameter H=0.95 (many high peaks). (many high peaks).
14.43. Message delay for fixed size message.
14.44. Message delay for Message delay for H=0.55 (longer response time peaks). (longer response time peaks).
14.45. Message delay for Message delay for H=0.95 (extremely long response time peak). (extremely long response time peak).
14.46. Settings.
14.47. New alert action.
14.48. Mailing information.
14.49. Settings.
14.50. Network topology.
15.1. SIMD architecture.
15.2. Bus-based SMP architecture.
15.3. ccNUMA architecture.
15.4. Ideal, typical, and super-linear speedup curves.
15.5. Locality optimisation by data transformation.
15.6. A simple MPI program.
15.7. Structure of an OpenMP program.
15.8. Matrix-vector multiply in OpenMP using a parallel loop.
15.9. Parallel random access machine.
15.10. Types of parallel random access machines.
15.11. A chain consisting of six processors.
15.12. A square of size A square of size 4\times4 ..
15.13. A 3-dimensional cube of size A 3-dimensional cube of size 2\times2\times2 ..
15.14. A 4-dimensional hypercube A 4-dimensional hypercube \mathcal{H}_{4} ..
15.15. A butterfly model.
15.16. A ring consisting of 6 processors.
15.17. Computation of prefixes of 16 elements using Optimal-Prefix .
15.18. Input data of array ranking and the the result of the ranking.
15.19. Work of algorithm Det-Ranking on the data of Example 15.4.
15.20. Sorting of 16 numbers by algorithm Odd-Even-Merge .
15.21. A work-optimal merge algorithm Optimal-Merge .
15.22. Selection of maximal integer number.
15.23. Prefix computation on square.
16.1. Rectangular systolic array for matrix product. (a) Array structure and input scheme. (b) Cell structure.
16.2. Two snapshots for the systolic array from Figure 16.1.
16.3. Hexagonal systolic array for matrix product. (a) Array structure and principle of the data input/output. (b) Cell structure.
16.4. Image of a rectangular domain under projection. Most interior points have been suppressed for clarity. Images of previous vertex points are shaded.
16.5. Partitioning of the space coordinates.
16.6. Detailed input/output scheme for the systolic array from Figure 16.3(a).
16.7. Extended input/output scheme, correcting Figure 16.6.
16.8. Interleaved calculation of three matrix products on the systolic array from Figure 16.3.
16.9. Resetting registers via global control. (a) Array structure. (b) Cell structure.
16.10. Output scheme with delayed output of results.
16.11. Combined local/global control. (a) Array structure. (b) Cell structure.
16.12. Matrix product on a rectangular systolic array, with output of results and distributed control. (a) Array structure. (b) Cell structure.
16.13. Matrix product on a rectangular systolic array, with output of results and distributed control. (a) Array structure. (b) Cell on the upper border.
16.14. Bubble sort algorithm on a linear systolic array. (a) Array structure with input/output scheme. (b) Cell structure.
17.1. Task system Task system \tau_{1} , and its optimal schedule., and its optimal schedule.
17.2. Scheduling of the task system Scheduling of the task system \tau_{1} at list L' . at list Scheduling of the task system \tau_{1} at list L' ..
17.3. Scheduling of the task system Scheduling of the task system \tau_{1} using list L on m'=4 processors. using list Scheduling of the task system \tau_{1} using list L on m'=4 processors. on Scheduling of the task system \tau_{1} using list L on m'=4 processors. processors.
17.4. Scheduling of Scheduling of \tau_{2} with list L on m=3 processors. with list Scheduling of \tau_{2} with list L on m=3 processors. on Scheduling of \tau_{2} with list L on m=3 processors. processors.
17.5. Scheduling task system Scheduling task system \tau_{3} on m=3 processors. on Scheduling task system \tau_{3} on m=3 processors. processors.
17.6. Task system Task system \tau and its optimal scheduling S_{\mbox{\texttt{\textit{OPT}}}} on two processors. and its optimal scheduling Task system \tau and its optimal scheduling S_{\mbox{\texttt{\textit{OPT}}}} on two processors. on two processors.
17.7. Optimal list scheduling of task system Optimal list scheduling of task system \tau' ..
17.8. Scheduling Scheduling S_{7}(\tau_{4}) belonging to list L=(T_{1},\dots,T_{n}) . belonging to list Scheduling S_{7}(\tau_{4}) belonging to list L=(T_{1},\dots,T_{n}) ..
17.9. Scheduling Scheduling S_{8}(\tau_{4}) belonging to list L' . belonging to list Scheduling S_{8}(\tau_{4}) belonging to list L' ..
17.10. Identical graph of task systems Identical graph of task systems \tau_{5} and \tau_{5}' . and Identical graph of task systems \tau_{5} and \tau_{5}' ..
17.11. Schedulings Schedulings S_{9}(\tau_{5}) and S_{10}(\tau_{5}') . and Schedulings S_{9}(\tau_{5}) and S_{10}(\tau_{5}') ..
17.12. Graph of the task system Graph of the task system \tau_{6} ..
17.13. Optimal scheduling Optimal scheduling S_{11}(\tau_{6}) ..
17.14. Scheduling Scheduling S_{12}(\tau_{6}') ..
17.15. Precedence graph of task system Precedence graph of task system \tau_{7} ..
17.16. The optimal scheduling The optimal scheduling S_{13}(\tau_{7}) (a=mm'-m'+3 , b=a+1 , c=mm'-m'+m+1 ). (The optimal scheduling S_{13}(\tau_{7}) (a=mm'-m'+3 , b=a+1 , c=mm'-m'+m+1 )., The optimal scheduling S_{13}(\tau_{7}) (a=mm'-m'+3 , b=a+1 , c=mm'-m'+m+1 )., The optimal scheduling S_{13}(\tau_{7}) (a=mm'-m'+3 , b=a+1 , c=mm'-m'+m+1 ).).
17.17. The optimal scheduling The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 ). (The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 )., The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 )., The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 )., The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 )., The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 )., The optimal scheduling S_{14}(\tau_{7}) (a=mm'-2m'+m+2 , b=m+1 , c=2m+2 , d=mm'-2m'+2m+2 , e=m+m'+1 , f=mm'-m'+m+1 ).).
17.18. Summary of the numbers of discs.
17.19. Pairwise comparison of algorithms.
17.20. Results of the pairwise comparison of algorithms.
18.1. Application of Join-test( Application of Join-test( R,F,\rho ) . ) .
19.1. The database CinePest.
19.2. The three levels of database architecture.
19.3. GMAPs for the university domain.
19.4. The graph The graph G ..
19.5. The graph The graph G' ..
19.6. A taxonomy of work on answering queries using views.
20.1. Edge-labeled graph assigned to a vertex-labeled graph.
20.2. An edge-labeled graph and the corresponding vertex-labeled graph.
20.3. The graph corresponding to the XML file “forbidden”.
20.4. A relational database in the semi-structured model.
20.5. The schema of the semi-structured database given in Figure 20.4.
21.1. The tree on which we introduce the Felsenstein algorithm. Evolutionary times are denoted with The tree on which we introduce the Felsenstein algorithm. Evolutionary times are denoted with v s on the edges of the tree.s on the edges of the tree.
21.2. A dendrogram.
21.3. Connecting leaf Connecting leaf n+1 to the dendrogram. to the dendrogram.
21.4. Calculating Calculating d_{u,k} according to the Centroid method. according to the Centroid method.
21.5. Connecting leaf Connecting leaf n+1 for constructing an additive tree. for constructing an additive tree.
21.6. Some tree topologies for proving Theorem 21.7.
21.7. The configuration of nodes The configuration of nodes i , j , k and l if i and j follows a cherry motif., The configuration of nodes i , j , k and l if i and j follows a cherry motif., The configuration of nodes i , j , k and l if i and j follows a cherry motif. and The configuration of nodes i , j , k and l if i and j follows a cherry motif. if The configuration of nodes i , j , k and l if i and j follows a cherry motif. and The configuration of nodes i , j , k and l if i and j follows a cherry motif. follows a cherry motif.
21.8. The possible places for node The possible places for node m on the tree. on the tree.
21.9. Representation of the Representation of the -1,\,+2,\,+5,\,+3,\,+4 signed permutation with an unsigned permutation, and its graph of desire and reality. signed permutation with an unsigned permutation, and its graph of desire and reality.
22.1. Functions defining the sphere, the block, and the torus.
22.2. Parametric forms of the sphere, the cylinder, and the cone, where Parametric forms of the sphere, the cylinder, and the cone, where u,v\in[0,1] ..
22.3. Parametric forms of the ellipse, the helix, and the line segment, where Parametric forms of the ellipse, the helix, and the line segment, where t\in[0,1] ..
22.4. A Bézier curve defined by four control points and the respective basis functions (A Bézier curve defined by four control points and the respective basis functions (m=3 ).).
22.5. Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.. Arrows indicate useful interval Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles. where we can find Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles. number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.
22.6. A B-spline interpolation. Based on points A B-spline interpolation. Based on points \vec{p}_{0},\ldots,\vec{p}_{m} to be interpolated, control points \vec{c}_{-1},\ldots,\vec{c}_{m+1} are computed to make the start and end points of the segments equal to the interpolated points. to be interpolated, control points A B-spline interpolation. Based on points \vec{p}_{0},\ldots,\vec{p}_{m} to be interpolated, control points \vec{c}_{-1},\ldots,\vec{c}_{m+1} are computed to make the start and end points of the segments equal to the interpolated points. are computed to make the start and end points of the segments equal to the interpolated points.
22.7. Iso-parametric curves of surface.
22.8. The influence decreases with the distance. Spheres of influence of similar signs increase, of different signs decrease each other.
22.9. The operations of constructive solid geometry for a cone of implicit function The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ). and for a sphere of implicit function The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).: union (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).), intersection (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).), and difference (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).).
22.10. Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, \setminus : difference).: difference).
22.11. Types of polygons. (a) simple; (b) complex, single connected; (c) multiply connected.
22.12. Diagonal and ear of a polygon.
22.13. The proof of the existence of a diagonal for simple polygons.
22.14. Tessellation of parametric surfaces.
22.15. Estimation of the tessellation error.
22.16. T vertices and their elimination with forced subdivision.
22.17. Construction of a subdivision curve: at each step midpoints are obtained, then the original vertices are moved to the weighted average of neighbouring midpoints and of the original vertex.
22.18. One smoothing step of the Catmull-Clark subdivision. First the face points are obtained, then the edge midpoints are moved, and finally the original vertices are refined according to the weighted sum of its neighbouring edge and face points.
22.19. Original mesh and its subdivision applying the smoothing step once, twice and three times, respectively.
22.20. Generation of the new edge point with butterfly subdivision.
22.21. Possible intersections of the per-voxel tri-linear implicit surface and the voxel edges. From the possible 256 cases, these 15 topologically different cases can be identified, from which the others can be obtained by rotations. Grid points where the implicit function has the same sign are depicted by circles.
22.22. Polyhedron-point containment test. A convex polyhedron contains a point if the point is on that side of each face plane where the polyhedron is. To test a concave polyhedron, a half line is cast from the point and the number of intersections is counted. If the result is an odd number, then the point is inside, otherwise it is outside.
22.23. Point in triangle containment test. The figure shows that case when point Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle. is on the left of oriented lines Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle. and Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle., and on the right of line Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle., that is, when it is not inside the triangle.
22.24. Point in triangle containment test on coordinate plane Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices.. Third vertex Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices. can be either on the left or on the right side of oriented line Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices., which can always be traced back to the case of being on the left side by exchanging the vertices.
22.25. Polyhedron-polyhedron collision detection. Only a part of collision cases can be recognized by testing the containment of the vertices of one object with respect to the other object. Collision can also occur when only edges meet, but vertices do not penetrate to the other object.
22.26. Clipping of simple convex polygon Clipping of simple convex polygon \vec{p}[0],\ldots,\vec{p}[5] results in polygon \vec{q}[0],\ldots,\vec{q}[4] . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane. results in polygon Clipping of simple convex polygon \vec{p}[0],\ldots,\vec{p}[5] results in polygon \vec{q}[0],\ldots,\vec{q}[4] . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.. The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.
22.27. When concave polygons are clipped, the parts that should fall apart are connected by even number of edges.
22.28. The 4-bit codes of the points in a plane and the 6-bit codes of the points in space.
22.29. The embedded model of the projective plane: the projective plane is embedded into a three-dimensional Euclidean space, and a correspondence is established between points of the projective plane and lines of the embedding three-dimensional Euclidean space by fitting the line to the origin of the three-dimensional space and the given point.
22.30. Ray tracing.
22.31. Partitioning the virtual world by a uniform grid. The intersections of the ray and the coordinate planes of the grid are at regular distances Partitioning the virtual world by a uniform grid. The intersections of the ray and the coordinate planes of the grid are at regular distances c_{x}/v_{x} , c_{y}/v_{y} , and c_{z}/v_{z} , respectively., Partitioning the virtual world by a uniform grid. The intersections of the ray and the coordinate planes of the grid are at regular distances c_{x}/v_{x} , c_{y}/v_{y} , and c_{z}/v_{z} , respectively., and Partitioning the virtual world by a uniform grid. The intersections of the ray and the coordinate planes of the grid are at regular distances c_{x}/v_{x} , c_{y}/v_{y} , and c_{z}/v_{z} , respectively., respectively.
22.32. Encapsulation of the intersection space by the cells of the data structure in a uniform subdivision scheme. The intersection space is a cylinder of radius Encapsulation of the intersection space by the cells of the data structure in a uniform subdivision scheme. The intersection space is a cylinder of radius r . The candidate space is the union of those spheres that may overlap a cell intersected by the ray.. The candidate space is the union of those spheres that may overlap a cell intersected by the ray.
22.33. A quadtree partitioning the plane, whose three-dimensional version is the octree. The tree is constructed by halving the cells along all coordinate axes until a cell contains “just a few” objects, or the cell sizes gets smaller than a threshold. Objects are registered in the leaves of the tree.
22.34. A kd-tree. A cell containing “many” objects are recursively subdivided to two cells with a plane that is perpendicular to one of the coordinate axes.
22.35. Notations and cases of algorithm Ray-First-Intersection-with-kd-Tree . Notations and cases of algorithm Ray-First-Intersection-with-kd-Tree . t_{in} , t_{out} , and t are the ray parameters of the entry, exit, and the separating plane, respectively. d is the signed distance between the ray origin and the separating plane., Notations and cases of algorithm Ray-First-Intersection-with-kd-Tree . t_{in} , t_{out} , and t are the ray parameters of the entry, exit, and the separating plane, respectively. d is the signed distance between the ray origin and the separating plane., and Notations and cases of algorithm Ray-First-Intersection-with-kd-Tree . t_{in} , t_{out} , and t are the ray parameters of the entry, exit, and the separating plane, respectively. d is the signed distance between the ray origin and the separating plane. are the ray parameters of the entry, exit, and the separating plane, respectively. Notations and cases of algorithm Ray-First-Intersection-with-kd-Tree . t_{in} , t_{out} , and t are the ray parameters of the entry, exit, and the separating plane, respectively. d is the signed distance between the ray origin and the separating plane. is the signed distance between the ray origin and the separating plane.
22.36. Kd-tree based space partitioning with empty space cutting.
22.37. Steps of incremental rendering. (a) Modelling defines objects in their reference state. (b) Shapes are tessellated to prepare for further processing. (c) Modelling transformation places the object in the world coordinate system. (d) Camera transformation translates and rotates the scene to get the eye to be at the origin and to look parallel with axis Steps of incremental rendering. (a) Modelling defines objects in their reference state. (b) Shapes are tessellated to prepare for further processing. (c) Modelling transformation places the object in the world coordinate system. (d) Camera transformation translates and rotates the scene to get the eye to be at the origin and to look parallel with axis -z . (e) Perspective transformation converts projection lines meeting at the origin to parallel lines, that is, it maps the eye position onto an ideal point. (f) Clipping removes those shapes and shape parts, which cannot be projected onto the window. (g) Hidden surface elimination removes those surface parts that are occluded by other shapes. (h) Finally, the visible polygons are projected and their projections are filled with their visible colours.. (e) Perspective transformation converts projection lines meeting at the origin to parallel lines, that is, it maps the eye position onto an ideal point. (f) Clipping removes those shapes and shape parts, which cannot be projected onto the window. (g) Hidden surface elimination removes those surface parts that are occluded by other shapes. (h) Finally, the visible polygons are projected and their projections are filled with their visible colours.
22.38. Parameters of the virtual camera: eye position Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect )., target Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect )., and vertical direction Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect )., from which camera basis vectors Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect ). are obtained, front Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect ). and back Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect ). clipping planes, and vertical field of view Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect ). (the horizontal field of view is computed from aspect ratio Parameters of the virtual camera: eye position \vec{eye} , target \vec{lookat} , and vertical direction \vec{up} , from which camera basis vectors \vec{u},\vec{v},\vec{w} are obtained, front f_{p} and back b_{p} clipping planes, and vertical field of view fov (the horizontal field of view is computed from aspect ratio aspect ).).
22.39. The normalizing transformation sets the field of view to 90 degrees.
22.40. The perspective transformation maps the finite frustum of pyramid defined by the front and back clipping planes, and the edges of the window onto an axis aligned, origin centred cube of edge size 2.
22.41. Notations of the Bresenham algorithm: Notations of the Bresenham algorithm: s is the signed distance between the closest pixel centre and the line segment along axis Y , which is positive if the line segment is above the pixel centre. t is the distance along axis Y between the pixel centre just above the closest pixel and the line segment. is the signed distance between the closest pixel centre and the line segment along axis Notations of the Bresenham algorithm: s is the signed distance between the closest pixel centre and the line segment along axis Y , which is positive if the line segment is above the pixel centre. t is the distance along axis Y between the pixel centre just above the closest pixel and the line segment., which is positive if the line segment is above the pixel centre. Notations of the Bresenham algorithm: s is the signed distance between the closest pixel centre and the line segment along axis Y , which is positive if the line segment is above the pixel centre. t is the distance along axis Y between the pixel centre just above the closest pixel and the line segment. is the distance along axis Notations of the Bresenham algorithm: s is the signed distance between the closest pixel centre and the line segment along axis Y , which is positive if the line segment is above the pixel centre. t is the distance along axis Y between the pixel centre just above the closest pixel and the line segment. between the pixel centre just above the closest pixel and the line segment.
22.42. Polygon fill. Pixels inside the polygon are identified scan line by scan line.
22.43. Incremental computation of the intersections between the scan lines and the edges. Coordinate Incremental computation of the intersections between the scan lines and the edges. Coordinate X always increases with the reciprocal of the slope of the line. always increases with the reciprocal of the slope of the line.
22.44. The structure of the active edge table.
22.45. A triangle in the screen coordinate system. Pixels inside the projection of the triangle on plane A triangle in the screen coordinate system. Pixels inside the projection of the triangle on plane XY need to be found. The Z coordinates of the triangle in these pixels are computed using the equation of the plane of the triangle. need to be found. The A triangle in the screen coordinate system. Pixels inside the projection of the triangle on plane XY need to be found. The Z coordinates of the triangle in these pixels are computed using the equation of the plane of the triangle. coordinates of the triangle in these pixels are computed using the equation of the plane of the triangle.
22.46. Incremental Incremental Z coordinate computation for a left oriented triangle. coordinate computation for a left oriented triangle.
22.47. Polygon-window relations: (a) distinct; (b) surrounding ; (c) intersecting; (d) contained.
22.48. A BSP-tree. The space is subdivided by the planes of the contained polygons.
23.1. 1000 shortest paths in a 100\times100 grid-graph, printed in overlap.shortest paths in a 1000 shortest paths in a 100\times100 grid-graph, printed in overlap. grid-graph, printed in overlap.
23.2. The graph for Examples 23.1, 23.2 and 23.6.
23.3. \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{1}=0.025,\;\varepsilon_{2}=0.050,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids.for \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{1}=0.025,\;\varepsilon_{2}=0.050,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids. on \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{1}=0.025,\;\varepsilon_{2}=0.050,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids. grids.
23.4. Example graph for the LP-penalty method.
23.5. An example for a non-unique decomposition in two paths.
23.6. \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{0}=0,\;\varepsilon_{1}=0.025,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids.for \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{0}=0,\;\varepsilon_{1}=0.025,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids. on \overline{\phi}_{\varepsilon_{i}} for \varepsilon_{0}=0,\;\varepsilon_{1}=0.025,\;\dots,\;\varepsilon_{30}=0.750 on 25\times25 grids. grids.
   Next