Efficient algorithms or approximation algorithms for Voronoi diagrams and triangulations, optimal decompositions and motion planning. See also Geometric Graph Algorithms.
Efficient approximation algorithms for Euclidean network problems including minimum-cost multi-connectivity, fault tolerant spanners and ``traveling salesperson''--type problems (also in the kinetic setting where the input objects move with different velocities in different directions ).
Efficient exact or approximation algorithms for subgraph isomorphism, graph packing, pattern matching and for fast network broadcasting.
Efficient methods for inferring evolutionary trees and efficient approximati on algorithms for string center problems.
Lower bounds and efficient construction methods for tree-like data structures for such basic problems as geometric range searching, priority search trees, static tree union-find and several problems from dynamic computational geometry. Efficient sequential and parallel algorithms for sorting, adaptive sorting and merging.
Sorting, searching and graph algorithms are classical topics in computer science. Computational geometry, parallel and distributed graph algorithms, and computational biology belong to the new frontier of computer science inspired by the rapid development of graphics, robotics, VLSI and parallel computing in recent years. The considered problems have applications in robotics, communication, databases, computer graphics, numerical analysis (in particular, terrain interpolation), cartography, chemistry, biology, and combinatorial optimization