Algorithms 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.
Author(s): Helmut Alt, Johannes Blömer (auth.), B. Monien, Th. Ottmann (eds.)
Series: Lecture Notes in Computer Science 594
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 395
Tags: Algorithm Analysis and Problem Complexity; Computer Graphics; Data Structures; Numerical Analysis; Database Management; Artificial Intelligence (incl. Robotics)
Resemblance and symmetries of geometric patterns....Pages 1-24
Selected topics from computational geometry, data structures and motion planning....Pages 25-43
Processing of hierarchically defined graphs and graph families....Pages 44-69
The combination of spatial access methods and computational geometry in geographic database systems....Pages 70-86
A flexible and extensible index manager for spatial database systems....Pages 87-103
The performance of object decomposition techniques for spatial query processing....Pages 104-123
Distributed image synthesis with breadth-first ray tracing and the ray-z-buffer....Pages 124-147
Restricted orientation computational geometry....Pages 148-185
Monotonous Bisector * Trees — a tool for efficient partitioning of complex scenes of geometric objects....Pages 186-203
Learning convex sets under uniform distribution....Pages 204-213
Spatial access structures for geometric databases....Pages 214-232
On spanning trees with low crossing numbers....Pages 233-249
High performance universal hashing, with applications to shared memory simulations....Pages 250-269
Distributed game tree search on a massively parallel system....Pages 270-288
Balanced strategies for routing on meshes....Pages 289-308
Complexity of Boolean functions on PRAMs - Lower bound techniques....Pages 309-329
Enumerative vs. genetic optimization two parallel algorithms for the bin packing problem....Pages 330-362
Area efficient methods to increase the reliability of circuits....Pages 363-389
