Local geometric properties with applications to parallel processing

partition the problem into subproblems that depend only on a part
of the input data. The partitioning can be done by a tessellation
of the output space of the algorithm. This leads to the question
which objects of the input determine the restriction of the problem
to a given query region. Such dependencies might be used to combine
locally computed parts to form a global solution. They are also of
interest by themselves.

Local dependencies have been discovered for several geometric
structures, for example for Voronoi diagrams and Delaunay
triangulations based on symmetric convex distance functions.
Surprisingly, these dependencies are non-canonical and require
certain conditions. Asymptotically optimal randomized parallel
algorithms on Coarse Grained Multicomputers have been developed
based on these results for planar Voronoi diagrams, Delaunay
triangulations and proximity graphs in colored point sets.