Data Structures and Efficient Algorithms

1. Front Matter

   PDF

2. Resemblance and symmetries of geometric patterns

   • Helmut Alt, Johannes Blömer

   Pages 1-24

3. Selected topics from computational geometry, data structures and motion planning

   • Rudolf Fleischer, Otfried Fries, Kurt Mehlhorn, Stefan Meiser, Stefan Näher, Hans Rohnert et al.

   Pages 25-43

4. Processing of hierarchically defined graphs and graph families

   • Franz Höfting, Thomas Lengauer, Egon Wanke

   Pages 44-69

5. The combination of spatial access methods and computational geometry in geographic database systems

   • Hans-Peter Kriegel, Thomas Brinkhoff, Ralf Schneider

   Pages 70-86

6. A flexible and extensible index manager for spatial database systems

   • Hans-Peter Kriegel, Peter Heep, Stephan Heep, Michael Schiwietz, Ralf Schneider

   Pages 87-103

7. The performance of object decomposition techniques for spatial query processing

   • Hans-Peter Kriegel, Holger Horn, Michael Schiwietz

   Pages 104-123

8. Distributed image synthesis with breadth-first ray tracing and the ray-z-buffer

   • Heinrich Müller, Jörg Winckler

   Pages 124-147

9. Restricted orientation computational geometry

   • Bengt J. Nilsson, Thomas Ottmann, Sven Schuierer, Christian Icking

   Pages 148-185

10. Monotonous Bisector* Trees — a tool for efficient partitioning of complex scenes of geometric objects

    • H. Noltemeier, K. Verbarg, C. Zirkelbach

    Pages 186-203

11. Learning convex sets under uniform distribution

    • Bernd Schmeltz

    Pages 204-213

12. Spatial access structures for geometric databases

    • Hans-Werner Six, Peter Widmayer

    Pages 214-232

13. On spanning trees with low crossing numbers

    • Emo Welzl

    Pages 233-249

14. High performance universal hashing, with applications to shared memory simulations

    • Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

    Pages 250-269

15. Distributed game tree search on a massively parallel system

    • R. Feldmann, P. Mysliwietz, B. Monien

    Pages 270-288

16. Balanced strategies for routing on meshes

    • Manfred Kunde, Thomas Tensi

    Pages 289-308

17. Complexity of Boolean functions on PRAMs - Lower bound techniques

    • Mirosław Kutyłowski

    Pages 309-329

18. Enumerative vs. genetic optimization two parallel algorithms for the bin packing problem

    • Berthold Kröger, Oliver Vornberger

    Pages 330-362

19. Area efficient methods to increase the reliability of circuits

    • Rüdiger Reischuk, Bernd Schmeltz

    Pages 363-389

20. Back Matter

    PDF

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.

• algorithm
• algorithms
• computational geometry
• computer
• computer graphics
• data structure
• data structures
• databases
• simulation
• tar
• algorithm analysis and problem complexity

Policies and ethics