## Data Structures and Efficient Algorithms: Final Report on the DFG Special Joint InitiativeAlgorithms are a central concept in computer science. The German Science Foundation (DFG) started a special joint initiative on data structures and efficient algorithms in 1986 with the aim of encouraging collaborative research on algorithms. For a period of five years about a dozen projects were funded with an emphasis on algorithms and data structures for geometric problems, on the one hand, and parallel and distributed algorithms, on the other. This volume contains 18 papers that are intended to give an impression of the achievements of this joint research initiative. The first group of papers addresses research on fundamental data structures, computational geometry, graph algorithms, computer graphics, and spatial databases. The second group of papers centers on the following problems: the design of parallel architectures and routing strategies, simulation of parallel machines, and the design of distributed algorithms for solving difficult problems. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Geometric Algorithms | 1 |

Selected Topics from Computational Geometry Data Structures and Motion Planning | 25 |

Processing of Hierarchically Defined Graphs and Graph Families | 44 |

The Combination of Spatial Access Methods and Computational Geometry in Geographic Database Systems | 70 |

A Flexible and Extensible Index Manager for Spatial Database Systems | 87 |

The Performance of Object Decomposition Techniques for Spatial Query Processing | 104 |

Distributed Image Synthesis with BreadthFirst Ray Tracing and the RayZBuffer | 124 |

Restricted Orientation Computational Geometry | 148 |

Spatial Access Structures for Geometric Databases | 214 |

On Spanning Trees with Low Crossing Numbers | 233 |

Parallel and Distributed Algorithms | 250 |

Distributed Game Tree Search on a Massively Parallel System | 270 |

Balanced Strategies for Routing on Meshes | 289 |

Complexity of Boolean Functions on PRAMsLower Bound Techniques | 309 |

Enumerative vs Genetic Optimization Two Parallel Algorithms for the Bin Packing Problem | 330 |

Area Efficient Methods to Increase the Reliability of Circuits | 363 |

Monotonous Bisector Treesa Tool for Efficient Partitioning of Complex Scenes of Geometric Objects | 186 |

Learning Convex Sets Under Uniform Distribution | 204 |

### Other editions - View all

### Common terms and phrases

applications approximation arbitrary attributes bisectors block Boolean function bounding box branch-&-bound cell cellular graph grammar circuit cluster index complexity components Computational Geometry Computer Science constant construction contains convex polygons convex sets CREW PRAM crossing number data structure database systems decomposition techniques defined denote distributed dynamic edges efficient Figure finite game tree genetic algorithm geometric objects given grid hash functions hierarchical implementation input integer intersection inverted indexes Lemma line segments linear lower bound monotone nodes nonterminal obstacle optimal orientations packets packing scheme parallel partition performance pin-graph plane sweep polynomial PRAM problem Proc query processing queue R*-tree random ray tracing rectangles redundancy regions representation routing shortest path simple polygons solution spatial access methods spatial database spatial objects spatial query split step storage stored strategy subproblems sweep line Theorem transposition table vertex vertices Voronoi Voronoi diagrams